- 题目描述：
-
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的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
本来是一道很简单的迪杰特斯拉算法，一开始提交的代码如下#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#define MAX 103
#define inf 0x3f3f3f3f
int map[MAX][MAX];
bool flag[MAX]; int main(int argc, char const *argv[])
{
int n, m;
scanf("%d %d",&n,&m);
while(n != || m != ) {
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
map[i][j] = inf;
flag[i] = false;
}
} int a,b,c;
for(int i = ; i < m; i++) {
scanf("%d %d %d",&a,&b,&c);
map[a][b] = c;
map[b][a] = c;
} flag[] = true;
int count = ;
while(count <= n) {
int min = MAX;
int mini = -;
for(int i = ; i <= n; i++) {
if(flag == false) {
if(map[][i] < min) {
min = map[][i];
mini = i;
}
}
}
map[][mini] = min;
flag[mini] = true;
for(int i = ; i <= n; i++) {
int dis = map[][mini] + map[mini][i];
if(dis < map[][i]) {
map[][i] = dis;
}
}
count++;
}
printf("%d\n",map[][n]);
scanf("%d %d",&n,&m);
}
return ;
}一开始百思不得其解究竟哪里做错了，只好先换一种写法
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#define MAX 103
#define inf 999999999
int map[MAX][MAX];
bool flag[MAX];
int lowCost[MAX]; int main(int argc, char const *argv[])
{
int n, m;
scanf("%d %d",&n,&m);
while(n != || m != ) {
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
map[i][j] = inf;
}
flag[i] = false;
} int a,b,c;
for(int i = ; i < m; i++) {
scanf("%d %d %d",&a,&b,&c);
map[a][b] = c;
map[b][a] = c;
} flag[] = true;
for(int i = ; i <= n; i++) {
lowCost[i] = map[][i];
} for(int i = ; i <= n; i++) {
int min = inf;
int v = -;
for(int j = ; j <= n; j++) {
if(flag[j] == false && lowCost[j] < min) {
min = lowCost[j];
v = j;
}
}
flag[v] = true; for(int j = ; j <= n; j++) {
if(flag[j] == false && lowCost[v]+map[v][j] < lowCost[j]) {
lowCost[j] = lowCost[v]+map[v][j];
}
}
} printf("%d\n",lowCost[n]);
scanf("%d %d",&n,&m);
}
return ;
}后来经仔细排查，第一种写法的错误有两处，一是33行,min = inf
二是36行flag[i] ==false
另一种办法是使用Floyd算法，但开始我的代码是这样的
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#define MAX 103
#define inf 999999999
int map[MAX][MAX]; int main(int argc, char const *argv[])
{
int n, m;
scanf("%d %d",&n,&m);
while(n != || m != ) {
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
map[i][j] = inf;
}
} for (int i=; i<=n; ++i)
map[i][i] = ; int a,b,c;
for(int i = ; i < m; i++) {
scanf("%d %d %d",&a,&b,&c);
map[a][b] = c;
map[b][a] = c;
} for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
for(int k = ; k <= n; k++) {
if (map[i][k] == inf || map[k][j] == inf)
continue;
if(map[i][k]+map[k][j] < map[i][j]) {
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
printf("%d\n",map[][n]);
scanf("%d %d",&n,&m);
}
return ;
}但WA了，而真正的算法是这样的
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#define MAX 103
#define inf 999999999
int map[MAX][MAX]; int main(int argc, char const *argv[])
{
int n, m;
scanf("%d %d",&n,&m);
while(n != || m != ) {
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
map[i][j] = inf;
}
} int a,b,c;
for(int i = ; i < m; i++) {
scanf("%d %d %d",&a,&b,&c);
map[a][b] = c;
map[b][a] = c;
} for(int k = ; k <= n; k++) {
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
if (map[i][k] == inf || map[k][j] == inf)
continue;
if(i != j && map[i][k] + map[k][j] < map[i][j]) {
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
printf("%d\n",map[][n]);
scanf("%d %d",&n,&m);
}
return ;
}注意算法是 先对中间点进行遍历，不断增加新的中间点以得到更优的答案