首页 > > 程序设计 > C/C++ >

【luogu 3371】【模板】单源最短路径

2018-06-17 21:51:26来源：未知阅读 ()

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式：

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

输入输出样例

输入样例#1：

输出样例#1：

0 2 4 3

说明

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=15

对于40%的数据：N<=100，M<=10000

对于70%的数据：N<=1000，M<=100000

对于100%的数据：N<=10000，M<=500000

样例说明：

题解：

Dijkstra：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 #include<vector>
 7 using namespace std;
 8 const int INF=0x3f;
 9 const int maxn=500050;
10 int d[maxn];bool vis[maxn];
11 vector<int> G[10004];
12 int n,m,sta;
13 struct Edge{int u,v,w;}e[maxn];
14 struct node{
15     int d,u;
16     bool operator < (const node &sky) const {
17         return sky.d<d;
18     }
19 };
20 void dijkstra(int sta){
21     priority_queue<node> q;
22     memset(d,INF,sizeof(d)); d[sta]=0;
23     q.push((node){0,sta});
24     while(!q.empty()){
25         node x=q.top();q.pop();
26         int u=x.u;
27         if(vis[u]) continue;
28         for(int i=0;i<G[u].size();i++){
29             Edge &edges=e[G[u][i]];
30             if(d[edges.v]>d[u]+edges.w){
31                 d[edges.v]=d[u]+edges.w;
32                 q.push((node){d[edges.v],edges.v});
33             }
34         }
35     }
36 }
37 int main(){
38     scanf("%d%d%d",&n,&m,&sta);
39     for(int i=1;i<=m;i++){
40         scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
41         G[e[i].u].push_back(i);
42     }
43     dijkstra(sta);
44     for(int i=1;i<=n;i++){
45         if(d[i]!=0x3f3f3f3f) printf("%d ",d[i]);
46         else printf("2147483647 ");
47     }
48     return 0;
49 }

Bellman-Ford：

不优化（70）：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 #include<vector>
 7 #define maxn 500005
 8 using namespace std;
 9 int read(){
10     int x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 int n,m,sta;
16 int u[maxn],v[maxn],w[maxn],d[maxn];
17 int main(){
18     n=read(),m=read(),sta=read();
19     for(int i=1;i<=n;i++) d[i]=0x3f3f3f3f;
20     d[sta]=0;
21     for(int i=1;i<=m;i++) u[i]=read(),v[i]=read(),w[i]=read();
22     for(int i=1;i<n;i++){
23         for(int j=1;j<=m;j++){
24             if(d[v[j]]>d[u[j]]+w[j]){
25                 d[v[j]]=d[u[j]]+w[j];
26             }
27         }
28     }
29     for(int i=1;i<=n;i++){
30         if(d[i]!=0x3f3f3f3f) printf("%d ",d[i]);
31         else printf("2147483647 ");
32     }
33     return 0;
34 }

剪枝优化（100）：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 #include<vector>
 7 #define maxn 500005
 8 using namespace std;
 9 int read(){
10     int x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 int n,m,sta;
16 int u[maxn],v[maxn],w[maxn],d[maxn];
17 int main(){
18     n=read(),m=read(),sta=read();
19     for(int i=1;i<=n;i++) d[i]=0x3f3f3f3f;
20     d[sta]=0;
21     for(int i=1;i<=m;i++) u[i]=read(),v[i]=read(),w[i]=read();
22     for(int i=1;i<n;i++){
23         bool flag=0;
24         for(int j=1;j<=m;j++){
25             if(d[v[j]]>d[u[j]]+w[j]){
26                 flag=true;
27                 d[v[j]]=d[u[j]]+w[j];
28             }
29         }
30         if(!flag) break;
31     }
32     for(int i=1;i<=n;i++){
33         if(d[i]!=0x3f3f3f3f) printf("%d ",d[i]);
34         else printf("2147483647 ");
35     }
36     return 0;
37 }

spfa：

邻接表版：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 #include<vector>
 7 #define maxn 10005
 8 using namespace std;
 9 int read(){
10     int x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 struct edge{int v,w;};
16 vector<edge>G[maxn];
17 int d[maxn],n,m,sta;
18 bool inq[maxn];
19 void add(int u,int v,int w){G[u].push_back((edge){v,w});}
20 void spfa(int sta){
21     memset(d,-1,sizeof(d));
22     d[sta]=0;
23     memset(inq,0,sizeof(inq));
24     queue<int> q;
25     q.push(sta);
26     while(!q.empty()){
27         int k=q.front(); q.pop();
28         inq[k]=0;
29         for(int i=0;i<G[k].size();i++){
30             edge &e=G[k][i];
31             if(d[e.v]==-1||d[k]+e.w<d[e.v]){
32                 d[e.v]=d[k]+e.w;
33                 if(!inq[e.v]){
34                     inq[e.v]=1;
35                     q.push(e.v);
36                 }
37             }
38         }
39     }
40 }
41 int main(){
42     n=read(),m=read(),sta=read();
43     int u,v,w;
44     for(int i=1;i<=m;i++){
45         u=read(),v=read(),w=read();
46         add(u,v,w);
47     }
48     spfa(sta);
49     for(int i=1;i<=n;i++){
50         if(d[i]==-1) printf("2147483647 ");
51         else printf("%d ",d[i]);
52     }
53     return 0;
54 }

前向星版：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 #include<vector>
 7 #define maxn 10005
 8 #define maxm 500005
 9 using namespace std;
10 int n,m,sta,last[maxn],cnt,inq[maxn],d[maxn];
11 int read(){
12     int x=0,f=1;char ch=getchar();
13     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
14     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
15     return x*f;
16 }
17 struct edge{int to,next,cost;}e[maxm];
18 void add(int x,int y,int z){e[++cnt].to=y;e[cnt].next=last[x];last[x]=cnt;e[cnt].cost=z;}
19 void spfa(int sta){
20     memset(d,-1,sizeof(d)); d[sta]=0;
21     memset(inq,0,sizeof(inq));
22     queue<int> q;
23     q.push(sta);
24     while(!q.empty()){
25         int k=q.front(); q.pop();
26         inq[k]=0;
27         for(int i=last[k];i;i=e[i].next){
28             int v=e[i].to;
29             if(d[v]==-1||d[v]>d[k]+e[i].cost){
30                 d[v]=d[k]+e[i].cost;
31                 if(!inq[v]){
32                     inq[v]=1;
33                     q.push(v);
34                 }
35             }
36         }
37     }
38 }
39 int main(){
40     n=read(),m=read(),sta=read();
41     int u,v,w;
42     for(int i=1;i<=m;i++){
43         u=read(),v=read(),w=read();
44         add(u,v,w);
45     }
46     spfa(sta);
47     for(int i=1;i<=n;i++){
48         if(d[i]==-1) printf("2147483647 ");
49         else printf("%d ",d[i]);
50     }
51     return 0;
52 }