Problem : 2544 ( 最短路 ) Judge Status : AcceptedRunId : 6003616 Language : C++ Author : qq1203456195Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta
1 #include <stdio.h>
2 #include <
string.h>
3 #include <stdlib.h>
4 #define MAX 0x3f3f3f3f
5 #define N 105
6 int cls[N],n,m;
7 int map[N][N];
8 int vis[N];
9 void Dijkstra(
int v)
10 {
11 int i,j,min,nxt;
12 for(i=
1;i<=n;i++) cls[i]=
map[v][i];
13 memset(vis,
0,
sizeof(vis));
14 vis[v]=
1;
15 for (i=
1;i<n;i++
)
16 {
17 min=
MAX;
18 nxt=
v;
19 for (j=
1;j<=n;j++
)
20 {
21 if(!vis[j]&&cls[j]<
min)
22 {
23 nxt=
j;
24 min=
cls[j];
25 }
26 }
27 vis[nxt]=
1;
28 for (j=
1;j<=n;j++
)
29 {
30 if(!vis[j]&&map[nxt][j]<MAX&&(min+map[nxt][j])<
cls[j])
31 cls[j]=cls[nxt]+
map[nxt][j];
32 }
33 }
34 }
35 int main()
36 {
37 int a,b,c;
38 while(scanf(
"%d%d",&n,&m),m||
n)
39 {
40 memset(map,MAX,
sizeof(map));
41 while (m--
)
42 {
43 scanf(
"%d%d%d",&a,&b,&
c);
44 if(map[a][b]>c) map[a][b]=map[b][a]=
c;
45 }
46 Dijkstra(
1);
47 printf(
"%d\n",cls[n]);
48 }
49 return 0;
50 }
转载于:https://www.cnblogs.com/CheeseZH/archive/2012/05/26/2519418.html
相关资源：数据结构—成绩单生成器
