最短路
发布日期:2021-08-14 02:31:38 浏览次数:1 分类:技术文章

本文共 1318 字,大约阅读时间需要 4 分钟。

spfa会被卡 试试dijskstra

没想到这个题写了 2h 结果是读入优化写错了

rio

#include
#include
#include
#include
#include
#include
#define maxn 500010 #define maxx 500010#define inf 2147483647using namespace std;//typedef pair
pa;//priority_queue
,greater
>q;priority_queue< pair
> q;int n,head[maxx];long long dis[maxx];int vis[maxx];int m,s,cnt;void read(int &x){ x=0;int flag=1;char c=getchar(); while(c<'0'||c>'9') flag=(c=='-'?-1:1),c=getchar(); while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); x=x*flag;}struct Edge{ int u,v; long long w;}edge[maxn];void add(int u,int v,long long w){ //nex edge[++cnt].v=v;//to edge[cnt].w=w;//v edge[cnt].u=head[u]; head[u]=cnt;//fr}void dijs(){ memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) dis[i]=inf; dis[s]=0; q.push(make_pair(0,s)); while(!q.empty()){ int now=q.top().second;q.pop(); if(vis[now]) continue; vis[now]=1; for(int i=head[now];i;i=edge[i].u){ int v=edge[i].v; if(dis[v]>dis[now]+edge[i].w) { dis[v]=dis[now]+edge[i].w; q.push(make_pair(-dis[v],v)); } } }} int main(){ read(n);read(m);read(s); for(int i=1;i<=m;i++){ int u,v,w; read(u);read(v);read(w); add(u,v,w); } dijs(); for(int i=1;i<=n;i++) cout<
<<" ";}

 

转载于:https://www.cnblogs.com/civilization-ga/p/9609480.html

转载地址:https://blog.csdn.net/weixin_30703911/article/details/95440270 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:JavaScript学习笔记——对象分类
下一篇:Spring Security(12)——Remember-Me功能

发表评论

最新留言

很好
[***.229.124.182]2024年03月21日 01时52分33秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php linux权限,Linux权限详细介绍 2021-06-24
典型环节的matlab仿真分析,典型环节的MATLAB仿真.doc 2021-06-24
Php contenttype类型,各种类型文件的Content Type 2021-06-24
php使用redis持久化,redis如何持久化 2021-06-24
php7.1解压包安装,【Swoole】php7.1安装swoole扩展 2021-06-24
linux centos删除安装的包,CentOS yum认为已删除的软件包仍在安装中 2021-06-24
酒店管理系统c语言带注释,酒店管理系统--C语言版.pdf 2019-04-21
c语言 实现sizeof功能,C语言简单实现sizeof功能代码 2019-04-21
c语言sin函数近似值,用泰勒公式求sin(x)的近似值 2019-04-21
c 语言登录系统源代码,c语言源代码---------------个人图书管理系统 2019-04-21
android线程通信方式,Android 主线程和子线程通信问题 2019-04-21
cps1 cps2 android,图文教程:CPS1和CPS2模拟器使用 2019-04-21
在线设计 html5 表单,html5注册表单制作-表单制作-小程序表单制作 2019-04-21
android小闹钟课程设计,《小闹钟》教学设计 2019-04-21
mysql文件系统_MySQL文件系统先睹为快(1) 2019-04-21
nums在python_程序找到一对(i,j),其中nums [i] + nums [j] +(i -j)在Python中最大化?... 2019-04-21
jquery后台内容管理_教育平台项目后台管理系统:课程内容模块 2019-04-21
grouping函数 mysql_sql聚合函数有哪些 2019-04-21
python os.walk如何不遍历隐藏文件_python 获取文件下所有文件或目录os.walk()的实例... 2019-04-21
python 股票估值_【中金固收·固收+】隐藏价值的角落:限售股AAP估值及Python实现方法(上)... 2019-04-21