hdu1874 畅通工程续

 1 #include<stdio.h>
 2 #define N 210
 3 #define M 0xffffff
 4 int D[N];//存放v0到其余节点的最短路径 
 5 int arc[N][N];//存放边的权值 
 6 int vexnum,arcnum;//村庄数及道路数 
 7 int ShortPath(int v0,int v1)
 8 {
 9      int v,w,k,min;
10      int vis[N];//标志数组，记录最小路径节点 
11      if(v0==v1) return 0;
12      for(v=0;v<vexnum;v++){
13             vis[v]=0;
14             D[v]=arc[v0][v];//D[]赋初值 
15      }
16      for(vis[v0]=v=1;v<vexnum;v++){
17             for(min=M,w=0;w<vexnum;w++)
18                 if(!vis[w]&&D[w]<min){//找当前权值最小的边 
19                     k=w;
20                     min=D[w];
21                 }
22             vis[k]=1;//加入最短路径序列 
23             for(w=0;w<vexnum;w++)
24                 if(!vis[w]&&(min+arc[k][w]<D[w]))//更新路径长度 
25                     D[w]=min+arc[k][w];
26      }
27      if(D[v1]==M) return -1;
28      else return D[v1];
29 }
30 int main()
31 {
32     int i,j,k,v0,v,w;
33     while(~scanf("%d%d",&vexnum,&arcnum))
34     {
35         for(i=0;i<vexnum;i++)
36             for(j=0;j<vexnum;j++)
37                 arc[i][j]=M;//赋初值，无穷大表无路径不可达 
38         for(k=0;k<arcnum;k++)
39         {
40             scanf("%d%d%d",&i,&j,&w);
41             if(w<arc[i][j])
42                 arc[j][i]=arc[i][j]=w;
43         }
44         scanf("%d%d",&v0,&v);
45         printf("%d\n",ShortPath(v0,v));
46     }
47     return 0;
48 }