在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的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条商店到赛场的路线。
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间。
| Sample Input | Sample Output |
|---|---|
2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0 |
3 2 |
#include <iostream> #include<cstdio> #include<string.h> using namespace std; int path[105][105]; int s[105]; bool use[105]; int main() { int n,m; scanf("%d%d",&n,&m); while (!((n==0)&(m==0))){ memset(path,1000000,sizeof(path)); memset(s,1000000,sizeof(s)); memset(use,true,sizeof(use)); s[1]=0; int j,k,l,g,h; j=m; while (j--){ scanf("%d%d%d",&g,&h,&l); path[g][h]=l; path[h][g]=l; } for (j=2;j<=n;j++) s[j]=path[1][j]; for (j=2;j<=n;j++){ l=10000000; for (k=2;k<=n;k++){ if ((s[k]<l)&&(use[k])){ l=s[k]; g=k; } } use[g]=false; for (k=2;k<=n;k++){ if (s[k]>s[g]+path[g][k]) s[k]=s[g]+path[g][k]; } } printf("%d\n",s[n]); scanf("%d%d",&n,&m); } return 0; }
原文：http://www.cnblogs.com/Atlantis67/p/3622128.html