Problem : 1874 ( 畅通工程续 ) Judge Status : AcceptedRunId : 5991510 Language : C++ Author : qq1203456195Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta
1 /*Dijstra*/
2 #include <iostream>
3 #include <cstring>
4 #include <cstdlib>
5 using namespace std;
6 #define MAX 0x3f3f3f3f
7 #define max 202
8 int map[max][max],visited[max];
9
10 int main()
11 {
12 int n,m,i,j,a,b,d;
13 while(cin>>n>>
m)
14 {
15 memset(map,MAX,
sizeof(map));
16 for(i=
0;i<n;i++
)
17 {
18 visited[i]=
0;
//访问标志位
19 map[i][i]=
0;
//注意
20 }
21 while(m--
)
22 {
23 cin>>a>>b>>
d;
24 if(map[a][b]>d) map[a][b]=map[b][a]=d;
/*注意可能会有多条路*/
25 }
26 cin>>a>>b;
//s 和 t
27 int min,u;
28 visited[a]=
1;
29 for(i=
0;i<n;i++
)
30 {
31 min=
MAX;
32 for(j=
0;j<n;j++
)
33 {
34 if(!visited[j]&&min>map[a][j])
//j没有被访问，且和a之间的距离最短，记录为u
35 {
36 min=map[a][j];
//min为a到j的距离
37 u=
j;
38 }
39 }
40 visited[u]=
1;
//u被访问了
41 for(j=
0;j<n;j++)
//更新a的邻接点
42 {
43 if(!visited[j]&&min+map[u][j]<map[a][j])
//j没有被访问，并且min+map[u][j]<map[a][j]
44 map[a][j]=min+
map[u][j];
45 }
46 }
47 if(map[a][b]<MAX) cout<<map[a][b]<<
endl;
48 else cout<<
"-1"<<
endl;
49 }
50 return 0;
51 }
转载于:https://www.cnblogs.com/CheeseZH/archive/2012/05/24/2517226.html
相关资源：数据结构—成绩单生成器
