https://vjudge.net/problem/HDU-2544
题意：
输入包括多组数据。每组数据第一行是两个整数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 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 #define INF 100000000 7 8 int n,m, A, B; 9 int map[205][205]; 10 int vis[205]; 11 int d[205]; 12 int num[205]; 13 14 void Dijkstra() 15 { 16 memset(vis, 0, sizeof(vis)); 17 for (int i = 2; i <= n; i++) 18 { 19 num[i] = map[1][i]; 20 } 21 num[1] = 0; 22 vis[1] = 1; 23 for (int i = 1; i < n; i++) 24 { 25 int min = INF; 26 int pos; 27 for (int j = 2; j <= n; j++) 28 { 29 if (num[j] < min && !vis[j]) 30 { 31 pos = j; 32 min = num[j]; 33 } 34 } 35 if (min == INF) break; 36 vis[pos] = 1; 37 for (int j = 1; j <= n; j++) 38 { 39 if (num[pos] + map[pos][j] < num[j] && !vis[j]) 40 num[j] = num[pos] + map[pos][j]; 41 } 42 } 43 printf("%d\n", num[n]); 44 } 45 46 int main() 47 { 48 //freopen("D:\\txt.txt", "r", stdin); 49 int a,b,c; 50 while (scanf("%d%d", &n,&m) && n && m) 51 { 52 for (int i = 1; i <= n; i++) 53 for (int j = 1; j <= n; j++) 54 map[i][j] = INF; 55 for (int i = 1; i <= m; i++) 56 { 57 scanf("%d%d%d", &a, &b, &c); 58 map[a][b] = map[b][a] = c; 59 } 60 Dijkstra(); 61 } 62 return 0; 63 }
原文：http://www.cnblogs.com/zyb993963526/p/6388781.html