首页 > 代码库 > P3371 【模板】单源最短路径

P3371 【模板】单源最短路径

2024-09-21 08:58:37   205人阅读

题目描述

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

输入输出格式

输入格式：

第一行包含三个整数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

说明

时空限制：1000ms,128M

数据规模：

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

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

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

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

样例说明：

技术分享

 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 }

 

P3371 【模板】单源最短路径


联系
我们