题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=2544
最短路
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 19055 Accepted Submission(s): 8125
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
Floyd算法 #include <stdio.h> #define oo (1 << 29) int map[105][105]; void cl(int n) { int i, j; for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) { if(i == j) map[i][j] = 0; else map[i][j] = oo; } } void Floyd(int n) { int i, j, k; for(k = 1; k <= n; k++) for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) if(map[i][j] > map[i][k] + map[k][j]) map[i][j] = map[i][k] + map[k][j]; } int main() { int n, m; int u, v, w; while(~scanf("%d %d",&n, &m) && (n || m)) { cl(n); while(m--) { scanf("%d %d %d",&u, &v, &w); if(map[u][v] > w) { map[u][v] = w; map[v][u] = w; } } Floyd(n); printf("%d\n",map[1][n]); } return 0; } Dijkstra算法 #include <stdio.h> #include <string.h> #define oo (1 << 29) int map[105][105], v[105], d[105]; void Dijkstra(int n) { int i; memset(v , 0 , sizeof(v)); for(i = 1; i <= n; i++) d[i] = map[1][i]; v[1] = 1; d[1] = 0; for(i = 1; i <= n; i++) { int x, y, m = oo; for(y = 1; y <= n; y++) { if(!v[y] && d[y] <= m) { m = d[x = y]; } } v[x] = 1; for(y = 1; y <= n; y++) { if(d[y] > d[x] + map[x][y]) d[y] = d[x] + map[x][y]; } } } int main() { int n, m, i, j; int u, v, w; while(~scanf("%d %d",&n, &m) && (n || m)) { for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) map[i][j] = oo; while(m--) { scanf("%d %d %d",&u, &v, &w); if(map[u][v] > w) { map[u][v] = w; map[v][u] = w; } } Dijkstra(n); printf("%d\n",d[n]); } return 0; }Bellman_ford算法 #include <stdio.h> #include <string.h> #include <iostream> #define oo 1 << 30 using namespace std; struct Eege { int u, v, w; } edge[11000]; int d[11000], n, m, t; int bellman_ford() { for(int i = 0; i <= n; i++) d[i] = oo; d[1] = 0; for(int i = 0; i < n-1; i++) { for(int j = 0; j < t; j++) { if(d[edge[j].v] > d[edge[j].u]+edge[j].w) d[edge[j].v] = d[edge[j].u]+edge[j].w; } } return d[n]; } int main() { int x, y, p; while(cin >>n>>m) { if(n == m && n == 0) break; t = 0; while(m--) { cin >>x>>y>>p; edge[t].u = x; edge[t].v = y; edge[t++].w = p; edge[t].u = y; edge[t].v = x; edge[t++].w = p; } printf("%d\n",bellman_ford()); } return 0; }