HDOJ 2544 Dijkstra实现

 1 #include <cstdio>
 2 #include <queue>
 3 #include <cstring>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 
 8 #define N 100
 9 #define Infinity 233333333
10 
11 int main(){
12     int n, m;
13     while (scanf("%d %d", &n, &m), n != 0){
14         int map[n][n];
15         int dis[n];
16         bool shortest[n];
17         for (int i = 0; i < n; i++)
18             for (int j = 0; j < n; j++)
19                 map[i][j] = Infinity;
20         for (int i = 0; i < m; i++){
21             int begin, end, temp;
22             scanf("%d %d %d", &begin, &end, &temp);
23             begin -= 1;
24             end -= 1;
25             map[begin][end] = min(map[begin][end], temp);
26             map[end][begin] = min(map[end][begin], temp);
27         }
28         for (int i = 0; i < n; i++){
29             dis[i] = map[0][i];
30             shortest[i] = 0;
31         }
32         while (1){
33             int current = 0;
34             for (int i = 1; i < n; i++)
35                 if (!shortest[i] && dis[i] < dis[current])
36                     current = i;
37             if (current == n - 1){
38                 printf("%d
", dis[current]);
39                 break;
40             }
41             shortest[current] = 1;
42             for (int i = 1; i < n; i++)
43                 if (dis[current] + map[current][i] < dis[i])
44                     dis[i] = dis[current] + map[current][i];
45         }
46     }
47     return 0;
48 }