HDU 2544 最短路（初涉SPFA算法）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2544

Problem Description

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

Input

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

Output

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

Sample Input

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

Sample Output

3 2

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<limits.h>
 5 #include<queue>
 6 using namespace std;
 7 #define maxn 1000000
 8 int n,m;
 9 int a[105][105];
10 int d[105];
11 bool vis[105];
12 int x,y,t;
13 void spfa(int i)
14 {
15     queue<int>Q;
16     Q.push(i);
17     vis[i]=true;
18     int cur;
19     while(!Q.empty())
20     {
21         cur=Q.front();
22         Q.pop();
23         vis[cur]=0;
24         int j;
25         for(j=1;j<=n;j++)
26         {
27             if(a[cur][j]+d[cur]<d[j])
28             {
29                 d[j]=a[cur][j]+d[cur];
30                 if(!vis[j])
31                 {
32                     vis[j]=true;
33                     Q.push(j);
34                 }
35             }
36         }
37     }
38 }
39 int main()
40 {
41     int i,j;
42     while(cin>>n>>m&&n&&m)
43     {
44         for(i=1;i<=n;i++)
45             for(j=1;j<=n;j++)
46             {
47                 if(i==j)a[i][j]=0;
48                 else a[i][j]=maxn;
49             }
50         for(i=1;i<=n;i++)
51         {
52             d[i]=maxn;
53         }
54         d[1]=0;
55         memset(vis,false,sizeof(vis));
56         //初始化结束
57         while(m--)
58         {
59             cin>>x>>y>>t;
60             if(t<a[x][y])
61             {
62                 a[x][y]=t;
63                 a[y][x]=t;
64             }
65         }
66         //读路完成
67         spfa(1);
68         cout<<d[n]<<endl;
69     }
70     return 0;
71 }