九度oj 题目1447：最短路

九度oj 题目1447：最短路

题目描述：

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

输入：

输入包括多组数据。每组数据第一行是两个整数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条商店到赛场的路线。
当输入为两个0时，输入结束。

输出：

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间。

样例输入：

2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

样例输出：

3
2
本来是一道很简单的迪杰特斯拉算法，一开始提交的代码如下

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #include <cmath>
 6 #define MAX 103
 7 #define inf 0x3f3f3f3f
 8 int map[MAX][MAX];
 9 bool flag[MAX];
10 
11 int main(int argc, char const *argv[])
12 {
13     int n, m;
14     scanf("%d %d",&n,&m);
15     while(n != 0 || m != 0) {
16         for(int i = 0; i <= n; i++) {
17             for(int j = 0; j <= n; j++) {
18                 map[i][j] = inf;
19                 flag[i] = false;
20             }
21         }
22 
23         int a,b,c;
24         for(int i = 0; i < m; i++) {
25             scanf("%d %d %d",&a,&b,&c);
26             map[a][b] = c;
27             map[b][a] = c;
28         }
29         
30         flag[1] = true;
31         int count = 1;
32         while(count <= n) {
33             int min = MAX;
34             int mini = -1;
35             for(int i = 1; i <= n; i++) {
36                 if(flag == false) {
37                     if(map[1][i] < min) {
38                         min = map[1][i];
39                         mini = i;
40                     }
41                 }
42             }
43             map[1][mini] = min;
44             flag[mini] = true;
45             for(int i = 1; i <= n; i++) {
46                 int dis = map[1][mini] + map[mini][i];
47                 if(dis < map[1][i]) {
48                     map[1][i] = dis;
49                 }
50             }
51             count++;
52         } 
53         printf("%dn",map[1][n]);
54         scanf("%d %d",&n,&m);
55     }
56     return 0;
57 }

一开始百思不得其解究竟哪里做错了，只好先换一种写法

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #include <cmath>
 6 #define MAX 103
 7 #define inf 999999999
 8 int map[MAX][MAX];
 9 bool flag[MAX];
10 int lowCost[MAX];
11 
12 int main(int argc, char const *argv[])
13 {
14     int n, m;
15     scanf("%d %d",&n,&m);
16     while(n != 0 || m != 0) {
17         for(int i = 0; i <= n; i++) {
18             for(int j = 0; j <= n; j++) {
19                 map[i][j] = inf;
20             }
21             flag[i] = false;
22         }
23 
24         int a,b,c;
25         for(int i = 0; i < m; i++) {
26             scanf("%d %d %d",&a,&b,&c);
27             map[a][b] = c;
28             map[b][a] = c;
29         }
30         
31         flag[1] = true;
32         for(int i = 1; i <= n; i++) {
33             lowCost[i] = map[1][i];
34         }
35 
36         for(int i = 1; i <= n; i++) {
37                 int min = inf;
38                 int v = -1;
39                 for(int j = 1; j <= n; j++) {
40                     if(flag[j] == false && lowCost[j] < min) {
41                         min = lowCost[j];
42                         v = j;
43                     }
44                 }
45                 flag[v] = true;
46  
47                 for(int j = 1; j <= n; j++) {
48                     if(flag[j] == false && lowCost[v]+map[v][j] < lowCost[j]) {
49                         lowCost[j] = lowCost[v]+map[v][j];
50                     }
51                 }
52         }
53 
54         printf("%dn",lowCost[n]);
55         scanf("%d %d",&n,&m);
56     }
57     return 0;
58 }

后来经仔细排查，第一种写法的错误有两处，一是33行,min = inf

二是36行flag[i] ==false

 

另一种办法是使用Floyd算法，但开始我的代码是这样的

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #include <cmath>
 6 #define MAX 103
 7 #define inf 999999999
 8 int map[MAX][MAX];
 9 
10 int main(int argc, char const *argv[])
11 {
12     int n, m;
13     scanf("%d %d",&n,&m);
14     while(n != 0 || m != 0) {
15         for(int i = 0; i <= n; i++) {
16             for(int j = 0; j <= n; j++) {
17                 map[i][j] = inf;
18             }
19         }
20 
21         for (int i=1; i<=n; ++i)  
22           map[i][i] = 0;  
23 
24         int a,b,c;
25         for(int i = 0; i < m; i++) {
26             scanf("%d %d %d",&a,&b,&c);
27             map[a][b] = c;
28             map[b][a] = c;
29         }
30         
31         for(int i = 1; i <= n; i++) {
32             for(int j = 1; j <= n; j++) {
33                 for(int k = 1; k <= n; k++) {
34                     if (map[i][k] == inf || map[k][j] == inf)  
35                         continue; 
36                     if(map[i][k]+map[k][j] < map[i][j]) {
37                         map[i][j] = map[i][k] + map[k][j];
38                     }
39                 }
40             }
41         }
42         printf("%dn",map[1][n]);
43         scanf("%d %d",&n,&m);
44     }
45     return 0;
46 }

但WA了，而真正的算法是这样的

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #include <cmath>
 6 #define MAX 103
 7 #define inf 999999999
 8 int map[MAX][MAX];
 9 
10 int main(int argc, char const *argv[])
11 {
12     int n, m;
13     scanf("%d %d",&n,&m);
14     while(n != 0 || m != 0) {
15         for(int i = 0; i <= n; i++) {
16             for(int j = 0; j <= n; j++) {
17                 map[i][j] = inf;
18             }
19         }
20 
21         int a,b,c;
22         for(int i = 0; i < m; i++) {
23             scanf("%d %d %d",&a,&b,&c);
24             map[a][b] = c;
25             map[b][a] = c;
26         }
27         
28         for(int k = 1; k <= n; k++) {
29             for(int i = 1; i <= n; i++) {
30                 for(int j = 1; j <= n; j++) {
31                     if (map[i][k] == inf || map[k][j] == inf)  
32                         continue; 
33                     if(i != j && map[i][k] + map[k][j] < map[i][j]) {
34                         map[i][j] = map[i][k] + map[k][j];
35                     }
36                 }
37             }
38         }
39         printf("%dn",map[1][n]);
40         scanf("%d %d",&n,&m);
41     }
42     return 0;
43 }

注意算法是 先对中间点进行遍历，不断增加新的中间点以得到更优的答案

转载于:.html