题目传送：http://hihocoder.com/problemset/problem/1081
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define INF 0x03F3F3F3F 5 #define N 1024 6 int path[N], vis[N]; 7 int cost[N][N],lowcost[N]; 8 void Dijkstra(int n, int beg){ 9 int i, j, min; 10 memset(vis, 0, sizeof(vis)); 11 vis[beg] = 1; 12 for (i=0; i<n; i++) 13 { 14 lowcost[i] = cost[beg][i]; path[i] = beg; 15 } 16 lowcost[beg] = 0; 17 path[beg] = -1; // 18 int pre = beg; 19 for (i=1; i<n; i++){ 20 min = INF; 21 for (j=0; j<n; j++) 22 if (vis[j]==0 && lowcost[pre]+cost[pre][j]<lowcost[j]) 23 { 24 lowcost[j] = lowcost[pre] + cost[pre][j]; 25 path[j] = pre; 26 } 27 for (j=0; j<n; j++) 28 if (vis[j] == 0 && lowcost[j] < min){ 29 min = lowcost[j]; pre = j; 30 } 31 vis[pre] = 1; 32 } 33 } 34 int main(){ 35 int n,m,s,t,i,k,a,b,c; 36 scanf("%d%d%d%d",&n,&m,&s,&t); 37 memset(cost,INF,sizeof(cost)); 38 for(i = 0 ;i<m;i++){ 39 scanf("%d%d%d",&a,&b,&c); 40 if(c<cost[a-1][b-1]){ 41 cost[a-1][b-1] = c; 42 cost[b-1][a-1] = c; 43 } 44 } 45 Dijkstra(n, s-1); 46 printf("%d ",lowcost[t-1]); 47 return 0; 48 }