杭电1874（畅通工程续）

最短路径求解
View Code
 1 //杭电1874（最短路径）
 2 #include<stdio.h>
 3 #define Max 10000
 4 int n,m,start,end;
 5 int a[210],b[210],map[210][210];
 6 void bfs()
 7 {
 8     int i,j,k,min;
 9     for(i=0;i<n;i++)
10         a[i]=map[start][i];
11     a[start]=0;
12     b[start]=1;
13     for(i=0;i<n;i++)
14     {
15         min=Max;
16         min=Max;
17         for(j=0;j<n;j++)
18         {
19             if(!b[j]&&min>a[j])
20             {
21                 min=a[j];
22                 k=j;
23             }
24         }
25         b[k]=1;
26         if(min==Max)
27             break;
28         for(j=0;j<n;j++)
29         {
30             if(!b[j]&&min+map[k][j]<a[j])
31                 a[j]=map[k][j]+min;
32         }
33     }
34     if(a[end]==Max)
35        printf("-1\n");
36     else
37         printf("%d\n",a[end]);
38 }
39 int main()
40 {
41     int i,j,x,y,z;
42     while(scanf("%d%d",&n,&m)!=-1)
43     {
44         for(i=0;i<n;i++)
45         {
46             a[i]=Max;
47             b[i]=0;
48             for(j=0;j<n;j++)
49                 map[i][j]=Max;
50         }
51         for(i=0;i<m;i++)
52         {
53             scanf("%d%d%d",&x,&y,&z);
54             if(map[x][y]>z)
55                 map[x][y]=map[y][x]=z;
56         }
57         scanf("%d%d",&start,&end);
58         bfs();
59     }
60     return 0;
61 }