题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1874
最短路Dijkstra模板题
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #define N 1000000 4 int map[250][250],visit[250],lowcost[250]; 5 void dis(int n,int s,int t) 6 { 7 int i,j,k,min; 8 for(i=0;i<n;i++) 9 { 10 visit[i]=0; 11 lowcost[i]=map[s][i]; 12 } 13 visit[s]=1; 14 for(i=1;i<n;i++) 15 { 16 min=N;k=-1; 17 for(j=0;j<n;j++) 18 { 19 if(visit[j]==0&&min>lowcost[j]) 20 { 21 min=lowcost[j]; 22 k=j; 23 } 24 } 25 if(k==-1) 26 break; 27 if(k==t) 28 break; 29 visit[k]=1; 30 for(j=0;j<n;j++) 31 { 32 if(visit[j]==0&&lowcost[j]>map[k][j]+lowcost[k]) 33 lowcost[j]=map[k][j]+lowcost[k]; 34 } 35 } 36 if(lowcost[t]==N) 37 printf("-1\n"); 38 else 39 printf("%d\n",lowcost[t]); 40 } 41 int main() 42 { 43 int n,m,i,j,a,b,x,s,t; 44 while(~scanf("%d%d",&n,&m)) 45 { 46 for(i=0;i<n;i++) 47 for(j=0;j<n;j++) 48 map[i][j]=N; 49 for(i=0;i<n;i++) 50 { 51 map[i][i]=0; 52 } 53 for(i=0;i<m;i++) 54 { 55 scanf("%d%d%d",&a,&b,&x); 56 if(x<map[a][b]) 57 { 58 map[a][b]=map[b][a]=x; 59 } 60 } 61 scanf("%d%d",&s,&t); 62 if(t==s) 63 { 64 printf("0\n"); 65 continue; 66 } 67 dis(n,s,t); 68 } 69 return 0; 70 }