dij 最短路径模板

#include<stdio.h> 

 int Path[550]; 

 int Dist[550]; 

 int Mark[550]; 

 int Map[550][550]; 

 void Dij(int x,int n) 

 { 

     int i,j,k; 

    for(i=1;i<=n;i++) 

     { 

         Dist[i]=Map[x][i]; 

         Mark[i]=1; 

         Path[i]=x; 

     } 

     Dist[x]=0; 

     Mark[x]=0; 

     Path[x]=-1; 

     int Min; 

     for(i=2;i<=n;i++) 

     { 

         Min=9999; 

         for(j=2;j<=n;j++) 

         { 

             if(Mark[j]&&Dist[j]<Min) 

             { 

                 k=j; 

                 Min=Dist[j]; 

             } 

         } 

         Mark[k]=0; 

         for(j=2;j<=n;j++) 

         { 

             if(Mark[j]) 

             if(Dist[k]+Map[k][j]<Dist[j]) 

             { 

                 Dist[j]=Dist[k]+Map[k][j]; 

                 Path[j]=k; 

             } 

         } 

     } 

 } 

 void Print(int n) 

 { 

     printf("%d\n",n); 

     while(Path[n]>0) 

     { 

         printf("%d\n",Path[n]); 

         n=Path[n]; 

     } 

 } 

 int main() 

 { 

     int n,m; 

     int x,y,z; 

     while(scanf("%d%d",&n,&m)!=EOF) 

     { 

         for(x=1;x<=n;x++) 

         { 

             for(y=x+1;y<=n;y++) 

                 Map[x][y]=Map[y][x]=9999; 

             Map[x][x]=0; 

         } 

         while(m--) 

         { 

             scanf("%d%d%d",&x,&y,&z); 

             Map[x][y]=Map[y][x]=z; 

         } 

         Dij(1,n); 

         Print(n); 

         printf("%d\n",Dist[n]); 

     } 

     return 0; 

 }