单源最短路径

来源:http://www.smjxgs.com 作者:王中王鉄算盘 人气:197 发布时间:2019-09-26
摘要:题目描述 如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。 题目描述 如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。 题目描述 如题,

题目描述

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

题目描述

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

题目描述

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

输入输出格式

输入格式:

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

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

输出格式:

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

输入输出格式

输入格式:

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

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

输出格式:

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

输入输出格式

输入格式:

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

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

输出格式:

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

输入输出样例

输入样例#1:

4 6 11 2 22 3 22 4 11 3 53 4 31 4 4

输出样例#1:

0 2 4 3

输入输出样例

输入样例#1:

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出样例#1:

0 2 4 3

输入输出样例

输入样例#1:

4 6 11 2 22 3 22 4 11 3 53 4 31 4 4

输出样例#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

样例说明:

图片 1

 1 #include<bits/stdc  .h> 2 using namespace std; 3 typedef long long ll; 4 ll read() 5 { 6 ll ret=0,ok=1; 7 char ch=getchar(); 8 while(ch<'0'||ch>'9') 9 {10 if(ch=='-')ok=-1;11 ch=getchar();12 }13 for(;ch>='0'&&ch<='9';ch=getchar14  ret=ret*10 ch-'0';15 return ret*ok;16 }17 const ll maxn=500000 10;18 const ll INF=~0u>>1;19 ll head[maxn],to[maxn],v[maxn],w[maxn],num,dis[maxn],vis[maxn],n,m,s,ans;20 struct node{21     ll d,pos;22     bool operator < (const node&pd) const {23     return d>pd.d;24     }25 }tmp;26 inline void get_node()27 {28     ll U,V,W;29     U=read(),V=read(),W=read();30     to[  num]=head[U],head[U]=num,v[num]=V,w[num]=W;31 }32 priority_queue <node> q;33 int main()34 {35 n=read(),m=read(),s=read();36 for(ll i=0;i<m;i  )37 dis[i]=INF;38 for(int i=1;i<=m;i  )39 get_node();40 dis[s]=0;41 q.push{0,s});42 while(!q.empty{43     tmp=q.top();44     q.pop();45     ll uu=tmp.pos;46     if47     continue;48     for(int h=head[tmp.pos],o=v[h];h;o=v[h=to[h]])49     {50         if(dis[o]>dis[uu] w[h]){51             dis[o]=dis[uu] w[h];52             q.push{dis[o],o});53         }    54     }55     vis[uu]=1;        56 }57 for(int i=1;i<=n;i  )58 cout<<dis[i]<<" ";59     return 0;60 }

说明

时空限制:1000ms,128M

数据规模:

对于20%的数据:N<=5,M<=15

对于40%的数据:N<=100,M<=10000

对于70%的数据:N<=1000,M<=100000

对于100%的数据:N<=10000,M<=500000

样例说明:

图片 2

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 const int MAXN=500001;
 8 struct node
 9 {
10     int u;
11     int v;
12     int w;
13     int next;
14 }edge[MAXN];
15 int num=1;
16 int head[MAXN];
17 void add(int x,int y,int z)
18 {
19     edge[num].u=x;
20     edge[num].v=y;
21     edge[num].w=z;
22     edge[num].next=head[x];
23     head[x]=num  ;
24 }
25 int dis[MAXN];
26 int vis[MAXN];
27 int n,m,s;
28 void SPFA(int s)
29 {
30     dis[s]=0;
31     vis[s]=1;
32     queue<int>q;
33     q.push(s);
34     while(q.size()!=0)
35     {
36         int p=q.front();
37         q.pop();
38         vis[p]=0;
39         for(int i=head[p];i!=-1;i=edge[i].next)
40         {
41             int to=edge[i].v;
42             if(dis[to]>dis[p] edge[i].w)
43             {
44                 dis[to]=dis[p] edge[i].w;
45                 if(vis[to]==0)
46                 {
47                     q.push(to);
48                     vis[to]=1;
49                 }
50             }
51         }
52     }
53     for(int i=1;i<=n;i  )
54     {
55         printf("%d ",dis[i]); 
56     }
57 }
58 int main()
59 {
60     
61     scanf("%d%d%d",&n,&m,&s);
62     for(int i=1;i<=n;i  )head[i]=-1,dis[i]=2147483647;
63     for(int i=1;i<=m;i  )
64     {
65         int x,y,z;
66         scanf("%d%d%d",&x,&y,&z);
67         add(x,y,z);
68     }
69     SPFA(s);
70     return 0;
71 }

 

说明

时空限制:1000ms,128M

数据规模:

对于20%的数据:N<=5,M<=15

对于40%的数据:N<=100,M<=10000

对于70%的数据:N<=1000,M<=100000

对于100%的数据:N<=10000,M<=500000

样例说明:

图片 3

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 using namespace std; 7 const int MAXN=500001; 8 struct node 9 {10     int u;11     int v;12     int w;13     int next;14 }edge[MAXN];15 int num=1;16 int head[MAXN];17 void add(int x,int y,int z)18 {19     edge[num].u=x;20     edge[num].v=y;21     edge[num].w=z;22     edge[num].next=head[x];23     head[x]=num  ;24 }25 int dis[MAXN];26 int vis[MAXN];27 int n,m,s;28 void SPFA(int s)29 {30     dis[s]=0;31     vis[s]=1;32     queue<int>q;33     q.push;34     while!=0)35     {36         int p=q.front();37         q.pop();38         vis[p]=0;39         for(int i=head[p];i!=-1;i=edge[i].next)40         {41             int to=edge[i].v;42             if(dis[to]>dis[p] edge[i].w)43             {44                 dis[to]=dis[p] edge[i].w;45                 if(vis[to]==0)46                 {47                     q.push;48                     vis[to]=1;49                 }50             }51         }52     }53     for(int i=1;i<=n;i  )54     {55         printf("%d ",dis[i]); 56     }57 }58 int main()59 {60     61     scanf("%d%d%d",&n,&m,&s);62     for(int i=1;i<=n;i  )head[i]=-1,dis[i]=2147483647;63     for(int i=1;i<=m;i  )64     {65         int x,y,z;66         scanf("%d%d%d",&x,&y,&z);67         add;68     }69     SPFA;70     return 0;71 }

本文由4887王中王鉄算盘奖结果发布于王中王鉄算盘,转载请注明出处:单源最短路径

关键词:

上一篇:git简明教程,Git使用教程

下一篇:没有了

最火资讯