本文主要是介绍P3371 【模板】单源最短路径(弱化版) spfa,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
P3371 【模板】单源最短路径(弱化版)
题目背景
本题测试数据为随机数据,在考试中可能会出现构造数据让SPFA不通过,如有需要请移步 P4779。
题目描述
如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。
输入输出格式
输入格式:
第一行包含三个整数N、M、S,分别表示点的个数、有向边的个数、出发点的编号。
接下来M行每行包含三个整数Fi、Gi、Wi,分别表示第i条有向边的出发点、目标点和长度。
输出格式:
一行,包含N个用空格分隔的整数,其中第i个整数表示从点S出发到点i的最短路径长度(若S=i则最短路径长度为0,若从点S无法到达点i,则最短路径长度为2147483647)
输入输出样例
输入样例#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
说明
时空限制:1000ms,128M
数据规模:
对于20%的数据:N<=5,M<=15;
对于40%的数据:N<=100,M<=10000;
对于70%的数据:N<=1000,M<=100000;
对于100%的数据:N<=10000,M<=500000。保证数据随机。
对于真正 100% 的数据,请移步 P4779。请注意,该题与本题数据范围略有不同。
样例说明:
图片1到3和1到4的文字位置调换
代码:
#include<bits/stdc++.h>
using namespace std;
#define INF 2147483647;
const int maxn=10005;
const int maxm=500005;
int n,m,s,cnt,a,b,c;
int dis[maxn],vis[maxn],head[maxm];
struct node
{int x,y,sum,next;
}e[maxm];
void add(int x,int y,int sum)
{cnt++;e[cnt].x=x;e[cnt].y=y;e[cnt].sum=sum;e[cnt].next=head[x];head[x]=cnt;
}//初始化
void spfa()
{queue<int>q;for(int i=1;i<=n;i++)dis[i]=INF;dis[s]=0;memset(vis,0,sizeof(vis));q.push(s);//入队 vis[s]=1;//初始化 while(!q.empty()){int u=q.front();q.pop();//出队 vis[u]=0;//出队标记 for(int i=head[u];i;i=e[i].next)//所有u能走的路 {int v=e[i].y;if(dis[v]>dis[u]+e[i].sum){dis[v]=dis[u]+e[i].sum;//取最小的 if(vis[v]==0)//如果这个点没在队列里就标记入队 {vis[v]=1;q.push(v);}}} }
}
int main()
{cin>>n>>m>>s;for(int i=1;i<=m;i++){cin>>a>>b>>c;add(a,b,c);}spfa();for(int i=1;i<=n;i++)cout<<dis[i]<<" ";return 0;
}
这篇关于P3371 【模板】单源最短路径(弱化版) spfa的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!