畅通工程续(dijskra+SPFA)

畅通工程续

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 67 Accepted Submission(s) : 37

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)，分别代表起点和终点。

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

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define MIN(x,y)(x<y?x:y)
 4 const int INF=0x3f3f3f3f;
 5 const int MAXN=1010;
 6 int d[MAXN];
 7 int N;
 8 int map[MAXN][MAXN],vis[MAXN];
 9 void initial(){
10     memset(map,INF,sizeof(map));
11     memset(vis,0,sizeof(vis));
12     memset(d,INF,sizeof(d));
13 }
14 void dijskra(int s){
15     d[s]=0;int k;
16     while(true){
17         k=-1;
18         for(int i=0;i<N;i++)
19             if(!vis[i]&&(k==-1||d[i]<d[k]))k=i;
20             if(k==-1)break;
21             vis[k]=1;
22         for(int i=0;i<N;i++){
23             d[i]=MIN(d[i],d[k]+map[k][i]);
24         }
25     }
26     }
27 int main(){
28     int M,a,b,c,e,s;
29     while(~scanf("%d%d",&N,&M)){
30             initial();
31         while(M--){
32             scanf("%d%d%d",&a,&b,&c);
33            if(c<map[a][b]) map[a][b]=map[b][a]=c;
34         }
35         scanf("%d%d",&s,&e); dijskra(s);
36         if(d[e]==0x3f3f3f3f)puts("-1");
37         else printf("%d
",d[e]);
38     }
39     return 0;
40     }

SPFA:

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<queue>
 4 using namespace std;
 5 const int INF=0x3f3f3f3f;
 6 const int MAXN=10010;
 7 const int MAXM=20010;
 8 int head[MAXM],edgnum;
 9 queue<int >dl;
10 struct Edge{
11     int from,to,value,next;
12 };
13 Edge edg[MAXM];
14 int N,M,vis[MAXN],dis[MAXN];
15 void add(int a,int b,int c){
16     Edge E={a,b,c,head[a]};
17     edg[edgnum]=E;
18     head[a]=edgnum++;
19 }
20 void put(){
21         int a,b,c;
22     while(M--){
23             scanf("%d%d%d",&a,&b,&c);
24             add(a,b,c);
25             add(b,a,c);
26         }
27 }
28 void initial(){
29     memset(head,-1,sizeof(head));
30     memset(vis,0,sizeof(vis));
31     memset(dis,INF,sizeof(dis));
32     while(!dl.empty())dl.pop();
33 }
34 void SPFA(int sx,int sy){
35     vis[sx]=1;
36     dis[sx]=0;
37     dl.push(sx);
38     while(!dl.empty()){
39         int k=dl.front();
40         dl.pop();
41         vis[k]=0;
42         for(int i=head[k];i!=-1;i=edg[i].next){
43             int v=edg[i].to;
44             if(dis[k]+edg[i].value<dis[v]){
45                 dis[v]=dis[k]+edg[i].value;
46                 if(!vis[v]){
47                 vis[v]=1;
48                 dl.push(v);
49             }
50             }
51         }
52     }
53     if(dis[sy]!=INF)printf("%d
",dis[sy]);
54     else puts("-1");
55 }
56 int main(){
57     int s,e;
58     while(~scanf("%d%d",&N,&M)){
59         initial();
60         put();
61         scanf("%d%d",&s,&e);
62         SPFA(s,e);
63     }
64     return 0;
65 }