SDUT 2622 最短路徑
Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description
為了準備一年一度的校賽，大家都在忙著往賽場搬運東西，比如氣球什么的。這時 YY 也沒有閑著，他也加入了搬運工的行列。已知學校有 N 個路口和 M 條路，YY 并不是把東西直接搬到賽場，而是從 S 路口搬運到 T 路口。由于 YY 非常懶而且他有輕度強迫癥。所以他要走的路需要盡可能的短，并且走過路徑的數(shù)目要為 X 的倍數(shù)。
Input
輸入的第一行為一個正整數(shù)T(1 ≤ T ≤ 20),代表測試數(shù)據(jù)組數(shù)。 對于每組測試數(shù)據(jù)： 輸入的第一行為兩個正整數(shù) N 和 M（1 ≤ N ≤ 100, 1 ≤ M ≤ 10000）。 接下來M行每行三個正整數(shù) U、V、W（0 ≤ U, V < N, 0 ≤ W ≤ 230 ），代表有一條從U到V的長度為W的有向路徑。 最后一行為三個正整數(shù)S、T 、X（0 ≤ S, T < N, 1 ≤ X ≤ 10）。
Output
對于每組測試數(shù)據(jù)，輸出滿足條件的從 S 到 T 的最短路徑。如果從 S 到 T 不可達，或者無法滿足路徑數(shù)是 X 的倍數(shù)，輸出“No Answer!”(不包含引號)。 注意：64-bit 整型請使用 long long 來定義，并且使用 %lld 或 cin、cout 來輸入輸出，請不要使用 __int64 和 %I64d。
Example Input
2 2 1 0 1 1 0 1 2 3 2 0 1 1 1 2 1 0 2 2
Example Output
No Answer! 2
Hint
在 SDUT 2894 C–最短路http://blog.csdn.net/yxc9806/article/details/56016361 的基礎(chǔ)上多了判斷是否為x倍數(shù)
Submit
#include <bits/stdc++.h>const long long INF = 0x3f3f3f3f3f3f3f3f;const int MAXN = 110;using namespace std;struct Edge{ int next; long long int u, v, w;} edge[100*MAXN];int N, M;int i, j, k;int s, t, x;int head[MAXN];long long int dist[MAXN][11];bool visit[MAXN];void spfa(){ queue<int>q; while(!q.empty()) q.pop(); memset(visit, 0, sizeof(visit)); for(i = 0; i <= N; i++) for(j = 0; j <= x; j++) dist[i][j] = INF; visit[s] = 1; dist[s][0] = 0; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); visit[u] = 0; for(i = head[u]; ~i; i = edge[i].next) { int v = edge[i].v; int w = edge[i].w; for(j = 0; j < x; j++) { if(dist[u][j] < INF && dist[v][(j+1)%x] > dist[u][j]+w) { dist[v][(j+1)%x] = dist[u][j] + w; if(!visit[v]) { visit[v] = 1; q.push(v); } } } } } if(dist[t][0] == INF) printf("No Answer!/n"); else printf("%lld/n", dist[t][0]);}int main(){ int T; scanf("%d", &T); long long int u, v, w; while(T--) { scanf("%d %d", &N, &M); int cnt = 0; memset(head, -1, sizeof(head)); for(i = 0; i < M; i++) { scanf("%lld %lld %lld", &u, &v, &w); edge[cnt].w = w; edge[cnt].u = u; edge[cnt].v = v; edge[cnt].next = head[u]; head[u] = cnt++; } scanf("%d %d %d", &s, &t, &x); spfa(); } return 0;}
