畅通工程续

杭电1874
View Code
 1 //1874畅通工程续
 2 #include<stdio.h>
 3 #include<string.h>
 4 #define Max 10005
 5 int f[Max][Max];
 6 int main()
 7 {
 8     int n,m,i,j,k,min,x,y,z,a,b;
 9     while(scanf("%d%d",&n,&m)!=-1)
10     {
11         for(i=0;i<n;i++)
12             for(j=0;j<n;j++)
13                 f[i][j]=Max;
14             for(i=0;i<n;i++)
15                 f[i][i]=0;
16             for(i=0;i<m;i++)
17             {
18                 scanf("%d%d%d",&x,&y,&z);
19                 if(f[x][y]>z||f[y][x]>z)
20                     f[x][y]=f[y][x]=z;
21             }
22             scanf("%d%d",&a,&b);
23             for(k=0;k<n;k++)
24             {
25                 for(i=0;i<n;i++)
26                     for(j=0;j<n;j++)
27                     {
28                         if(f[i][j]>f[i][k]+f[k][j])
29                             f[i][j]=f[i][k]+f[k][j];
30                     }
31             }
32             if(f[a][b]<Max)
33                 printf("%d\n",f[a][b]);
34             else
35                 printf("-1\n");
36     }
37     return 0;
38 }