Problem Description
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
Input
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
输入保证至少存在1条商店到赛场的路线。
Output
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
Sample Input
2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0
Sample Output
3 2
dijkstra算法：
1 #include<stdio.h> 2 #define INF 0x3f3f3f3f 3 #define N 1010 4 int vis[N], dis[N], cost[N][N]; 5 int n, m, s, w, p, q, t; 6 int min(int x, int y) 7 { 8 9 return x < y ? x : y; 10 } 11 void dijkstra(int beg) 12 { 13 int u, v; 14 for(u = 1; u <= n; u++) 15 { 16 vis[u] = 0; 17 dis[u] = INF; 18 } 19 dis[beg] = 0; 20 while(true) 21 { 22 v = -1; 23 for(u = 1; u <= n; u++) 24 if(!vis[u] && (v == -1 || dis[u] < dis[v])) 25 v = u; 26 if(v == -1) 27 break; 28 vis[v] = 1; 29 for(u = 1; u <= n; u++) 30 dis[u] = min(dis[u], dis[v] + cost[v][u]); 31 } 32 } 33 int main() 34 { 35 int i , j; 36 while(~scanf("%d%d%d", &n, &m, &s)) 37 { 38 for(i = 1; i <= n; i++) 39 for(j = i; j <= n; j++) 40 cost[i][j] = cost[j][i] = INF; 41 while(m--) 42 { 43 scanf("%d%d%d", &p, &q, &t); 44 if(cost[q][p] > t) 45 cost[q][p] = t; 46 } 47 scanf("%d", &w); 48 int sum = INF, b; 49 dijkstra(s); 50 for(i = 1; i <= w; i++) 51 { 52 scanf("%d", &b); 53 if(sum > dis[b]) 54 sum = dis[b]; 55 } 56 57 if(sum == INF) 58 printf("-1 "); 59 else 60 printf("%d ", sum); 61 } 62 return 0; 63 }
spfa代码：
1 #include <stdio.h> 2 #include <string.h> 3 #include <queue> 4 #define INF 0x3f3f3f3f 5 using namespace std; 6 int n, m, head[110]; 7 int used[110], vis[110], dis[110]; 8 struct node 9 { 10 int from, to, val, next; 11 }edge[10010]; 12 int cnt; 13 int add(int x, int y, int z) 14 { 15 edge[cnt].from = x; 16 edge[cnt].to = y; 17 edge[cnt].val = z; 18 edge[cnt].next = head[x]; 19 head[x] = cnt++; 20 } 21 void spfa(int s) 22 { 23 priority_queue <int> q; 24 memset(dis, INF, sizeof(dis)); 25 memset(used, 0, sizeof(used)); 26 dis[s] = 0; 27 vis[s] = 1; 28 q.push(s); 29 used[s]++; 30 while(!q.empty()) 31 { 32 int x; 33 x = q.top(); q.pop(); 34 vis[x] = 0; 35 for(int i = head[x]; i != -1; i = edge[i].next) 36 { 37 int y = edge[i].to; 38 if(dis[y] > dis[x]+edge[i].val) 39 { 40 dis[y] = dis[x]+edge[i].val; 41 if(!vis[y]) 42 { 43 q.push(y); 44 used[y]++; 45 vis[y] = 1; 46 if(used[y] > n) 47 { 48 return ; 49 } 50 } 51 } 52 } 53 } 54 if(q.empty()) 55 printf("%d ", dis[n]); 56 return ; 57 } 58 int main() 59 { 60 while(~scanf("%d%d", &n, &m), n&&m) 61 { 62 int k = 0; 63 cnt = 0; 64 memset(head, -1, sizeof(head)); 65 memset(vis, 0, sizeof(vis)); 66 for(int i = 0; i < m; i++) 67 { 68 int a, b, c; 69 scanf("%d%d%d", &a, &b, &c); 70 add(a, b, c); 71 add(b, a, c); 72 } 73 spfa(1); 74 } 75 return 0; 76 }