【模板】堆优化的dijkstra
2024-09-06 21:40:27
生命算法,以防忘记
#include<bits/stdc++.h>
using namespace std;
int head[200005],dis[200005],n,m,s,f,g,w,l;
bool sign[200005];
struct node
{
int to,next,val;
} a[200005];
inline void in(int from,int to,int v)
{
a[++l].next=head[from];
a[l].to=to;
a[l].val=v;
head[from]=l;
}
priority_queue < pair<int,int> >q;
inline void dijkstra()
{
for(register int i=1; i<=n; i++)
dis[i]=2147483647;
dis[s]=0;
q.push(make_pair(0,s));
while(q.size())
{
int x=q.top().second;
q.pop();
if(sign[x])continue;
sign[x]=1;
for(register int i=head[x]; i; i=a[i].next)
if(dis[a[i].to]>dis[x]+a[i].val)
{
dis[a[i].to]=dis[x]+a[i].val;
q.push(make_pair(-dis[a[i].to],a[i].to));
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(register int i=1; i<=m; i++)
{
scanf("%d%d%d",&f,&g,&w);
in(f,g,w);
}
dijkstra();
for(register int i=1; i<=n; i++)
printf("%d ",dis[i]);
return 0;
}
最新文章
- css浏览器窗口大小
- Android MultiDex兼容包怎么使用?
- JVMInternals
- 母函数入门笔记(施工中&hellip;
- VS2015 Cordova Ionic移动开发(五)
- c#常用方法和类
- Ubuntu安装genymotion模拟器步骤
- How Tomcat Works 读书笔记 八 载入器 上
- centos7初上手1-安装mysql数据库
- supervisor 守护进程
- 网络编程 -- RPC实现原理 -- Netty -- 迭代版本V3 -- 编码解码
- ThreadLocal 的机制与内存泄漏
- asp mvc 导出txt 文件泛型方法
- MySQL数据库图文安装详解及相关问题
- Ubuntu16.04上用源代码安装ICE
- 【内核】linux2.6版本内核编译配置选项(一)
- QQ彩票任意订阅内容导致骚扰用户
- hdoj1003 DP
- vue-cli脚手架安装
- Python学习笔记(六)—元组的操作