1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #define Max 0xfffffff 5 int m[10010][10010],p[10010]; 6 bool vis[10010]; 7 int vexnum,arcnum; 8 void dijstra() 9 { 10 int i,j,k,t,min; 11 memset(vis,0,sizeof(vis)); 12 for(i=1;i<=vexnum;++i) 13 p[i]=m[1][i]; 14 for(vis[1]=k=1;k<vexnum;++k){ 15 for(min=Max,i=1;i<=vexnum;++i) 16 if(!vis[i]&&min>p[i]){ 17 min=p[i]; 18 t=i; 19 } 20 vis[t]=1; 21 for(i=1;i<=vexnum;++i) 22 if(!vis[i]&&p[i]>min+m[t][i]) 23 p[i]=min+m[t][i]; 24 } 25 } 26 int main() 27 { 28 int i,j,a,b,w; 29 while(~scanf("%d%d",&vexnum,&arcnum),vexnum||arcnum){ 30 for(i=1;i<=vexnum;++i) 31 for(j=1;j<=vexnum;++j) 32 m[i][j]=m[j][i]=Max; 33 for(i=0;i<arcnum;++i){ 34 scanf("%d%d%d",&a,&b,&w); 35 m[a][b]=m[b][a]=w; 36 } 37 dijstra(); 38 printf("%d\n",p[vexnum]); 39 } 40 system("pause"); 41 return 0; 42 }
//很裸的dijstra