畅通工程续
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 41528 Accepted Submission(s): 15342
Problem Description
某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
Input
本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
Output
对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1
Author
linle
Source
2008浙大研究生复试热身赛（2）——全真模拟
Recommend
lcy | We have carefully selected several similar problems for you:
1142
1690
1385
2680
1879
最短路的模板题，注意城镇分别以0～N-1编号。
题意：中文题，很好理解。
附上代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #define M 205 5 #define MAX 0x3f3f3f3f 6 using namespace std; 7 int map[M][M],vis[M],dis[M]; 8 9 int main() 10 { 11 int n,m,i,j; 12 while(~scanf("%d%d",&n,&m)) 13 { 14 memset(vis,0,sizeof(vis)); 15 memset(dis,0,sizeof(dis)); 16 for(i=0; i<n; i++) 17 for(j=0; j<n; j++) 18 { 19 if(i==j) map[i][j]=0; 20 else map[i][j]=MAX; 21 } 22 int a,b,c; 23 while(m--) 24 { 25 scanf("%d%d%d",&a,&b,&c); 26 if(map[a][b]>c) 27 map[a][b]=c,map[b][a]=c; 28 } 29 int s,t; 30 scanf("%d%d",&s,&t); 31 vis[s]=1; 32 for(i=0; i<n; i++) 33 dis[i]=map[s][i]; 34 int min,k; 35 for(i=0; i<n; i++) 36 { 37 min=MAX; 38 for(j=0; j<n; j++) 39 if(!vis[j]&&min>dis[j]) 40 { 41 min=dis[j]; 42 k=j; 43 } 44 vis[k]=1; 45 for(j=0; j<n; j++) 46 if(!vis[j]&&map[k][j]<MAX) 47 if(dis[j]>dis[k]+map[k][j]) 48 dis[j]=dis[k]+map[k][j]; 49 } 50 if(dis[t]<MAX) 51 printf("%d\n",dis[t]); 52 else 53 printf("-1\n"); 54 } 55 return 0; 56 }
邻接表：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #define N 205 6 #define M 1005 7 #define INF 0x3f3f3f3f 8 using namespace std; 9 struct Edge 10 { 11 int from,to,val; 12 int next; 13 } edge[M*2]; 14 int n,m,tol,s,t; 15 int dis[N]; 16 bool vis[N]; 17 int head[M*2]; 18 19 void init() 20 { 21 tol=0; 22 memset(head,-1,sizeof(head)); 23 } 24 25 void addEdge(int u,int v,int w) 26 { 27 edge[tol].from=u; 28 edge[tol].to=v; 29 edge[tol].val=w; 30 edge[tol].next=head[u]; 31 head[u]=tol++; 32 edge[tol].from=v; 33 edge[tol].to=u; 34 edge[tol].val=w; 35 edge[tol].next=head[v]; 36 head[v]=tol++; 37 } 38 39 40 void getmap() 41 { 42 int a,b,c; 43 while(m--) 44 { 45 scanf("%d%d%d",&a,&b,&c); 46 addEdge(a,b,c); 47 } 48 scanf("%d%d",&s,&t); 49 memset(vis,false,sizeof(vis)); 50 memset(dis,INF,sizeof(dis)); 51 } 52 53 void spfa() 54 { 55 queue<int>q; 56 q.push(s); 57 dis[s]=0; 58 vis[s]=true; 59 while(!q.empty()) 60 { 61 int u=q.front(); 62 q.pop(); 63 vis[u]=false; 64 for(int i=head[u]; i!=-1; i=edge[i].next) 65 { 66 int v=edge[i].to; 67 if(dis[v]>dis[u]+edge[i].val) 68 { 69 dis[v]=dis[u]+edge[i].val; 70 if(!vis[v]) 71 { 72 vis[v]=true; 73 q.push(v); 74 } 75 } 76 } 77 } 78 if(dis[t]<INF) 79 printf("%d\n",dis[t]); 80 else 81 printf("-1\n"); 82 return; 83 } 84 85 int main() 86 { 87 88 int i,j; 89 while(~scanf("%d%d",&n,&m)) 90 { 91 if(n==0&&m==0) 92 break; 93 init(); 94 getmap(); 95 spfa(); 96 } 97 return 0; 98 }