dij 邻接表

#include<stdio.h> 

 #include<string.h> 

 struct Ele 

 { 

     int to; 

     int w; 

     int next; 

 } p[100000]; 

 int head[100000]; 

 int lowcost[100000]; 

 bool Mark[100000]; 

 int e; 

 void Dij(int x,int n) 

 { 

     int i,j,k; 

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

        lowcost[i]=99999999; 

     for(i=head[x];i!=-1;i=p[i].next) 

         lowcost[p[i].to]=p[i].w; 

     lowcost[x]=0; 

     Mark[x]=true; 

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

     { 

         int Min=99999999; 

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

             if(!Mark[j]&&lowcost[j]<Min) 

             { 

                 k=j; 

                 Min=lowcost[j]; 

             } 

         Mark[k]=true; 

         for(j=head[k];j!=-1;j=p[j].next) 

         { 

             
if(!Mark[p[j].to]&&lowcost[p[j].to]>lowcost[k]+p[j].w)//mark[p[j].to] 

                     lowcost[p[j].to]=lowcost[k]+p[j].w; 

         } 

     } 



 } 

 void Add(int x,int y,int z) 

 { 

     p[e].to=y; 

     p[e].w=z; 

     p[e].next=head[x]; 

     head[x]=e++; 

 } 

 int main() 

 { 

     int n,m; 

     int x,y,z; 

     while(scanf("%d%d",&n,&m),n&&m) 

     { 

         e=0; 

         memset(head,-1,sizeof(head)); 

         while(m--) 

         { 

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

             Add(x,y,z); 

             Add(y,x,z); 

         } 

         memset(Mark,false,sizeof(Mark)); 

         Dij(1,n); 

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

     } 

     return 0; 

 }