最短路径 dijkstra

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <limits.h>
 4 
 5 #define MAX INT_MAX
 6 #define N    100
 7 
 8 int map[N][N];
 9 int len[N];
10 int vis[N];
11 int n;
12 
13 void build() {
14 
15     int i, j;
16     int u, v, c;
17     int m; 
18     
19     scanf("%d", &n);
20     memset(map, -1, sizeof(map));
21     scanf("%d", &m);
22     while(m--) {
23         scanf("%d%d%d", &u, &v, &c);
24         map[u][v] = c;
25     }
26 
27 //    scanf("%d", &s);
28 }
29 
30 void dij() {
31 
32     int min;
33     int i, t;
34 
35     memset(vis, 0, sizeof(vis));
36     for(i = 0; i <= n; i++)
37         len[i] = MAX;
38     len[0] = 0;
39 
40     while(1) {
41         min = n;
42         for(i = 0; i < n; i++){
43             if(vis[i]) continue;
44             if(len[i] < len[min])
45                 min = i;
46         }
47 
48         if(min == n) break;
49         printf("min = %d
", min);
50         vis[min] = 1;
51 
52         for(i = 0; i < n; i++) {
53             if(vis[i] || map[min][i] == -1) continue;
54             t = len[min] + map[min][i];
55             if(len[i] > t)
56                 len[i] = t;
57          }
58     }
59 
60 }
61 
62 void show() {
63 
64     int i, j;
65     for(i = 0; i < n; i++) {
66         for(j = 0; j < n; j++)
67             printf("%-5d", map[i][j]);
68         printf("
");
69     }
70     printf("

");
71 
72     for(i = 0; i < n; i++)
73         printf("%d, ", len[i]);
74     printf("

");
75 }
76 
77 
78 int main(int argc, char const *argv[])
79 {
80     freopen("duan","r",stdin);
81     build();
82     dij();
83     show();
84 
85     return 0;
86 }
87 /*
88 6 8
89 0 5 100
90 0 2 10
91 0 4 30
92 1 2 5
93 2 3 50
94 3 5 10
95 4 3 20
96 4 5 60
97 */