HDU 2544 最短路（Dijkstra）

题意：

输入包括多组数据。每组数据第一行是两个整数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
", 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 }