P3371 【模板】单源最短路径(弱化版) spfa

2024-04-12 10:58

本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/896940

相关文章

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径,

基于Java实现模板填充Word

《基于Java实现模板填充Word》这篇文章主要为大家详细介绍了如何用Java实现按产品经理提供的Word模板填充数据,并以word或pdf形式导出,有需要的小伙伴可以参考一下... Java实现按模板填充wor编程d本文讲解的需求是:我们需要把数据库中的某些数据按照 产品经理提供的 word模板,把数据

python获取当前文件和目录路径的方法详解

《python获取当前文件和目录路径的方法详解》:本文主要介绍Python中获取当前文件路径和目录的方法,包括使用__file__关键字、os.path.abspath、os.path.realp... 目录1、获取当前文件路径2、获取当前文件所在目录3、os.path.abspath和os.path.re

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i