「LuoguP4779」【模板】单源最短路径（标准版）

mac2022-06-30 21

Description

2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程一题里非常熟练地使用了一个广为人知的算法求最短路。

然后呢？

100→60；

Ag→Cu；

最终，他因此没能与理想的大学达成契约。

小 F 衷心祝愿大家不再重蹈覆辙。

题目描述

给定一个 N 个点， M 条有向边的带非负权图，请你计算从 S 出发，到每个点的距离。

数据保证你能从 S 出发到任意点。

Input

第一行为三个正整数 N,M,S 。第二行起 M 行，每行三个非负整数 ui,vi,wi ，表示从 ui 到 vi 有一条权值为 wi 的边。

Output

输出一行 N 个空格分隔的非负整数，表示 S 到每个点的距离。

Sample Input

4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4

Sample Output

0 2 4 3

Hint

样例解释请参考数据随机的模板题。

1 ≤ N ≤ 100000；

1 ≤ M ≤ 200000；

S=1；

1 ≤ ui , vi ≤ N ；

0 ≤ wi ≤ 1e9 ,

0 ≤ ∑ wi ≤ 1e9 。

题解

8012年7月19日，SPFA终于还是迎来了被官方审判的日子。

SPFA的光辉梦幻般消逝。

以前从来没写过堆优dijkstra，SPFA这么香用什么堆优

会了重载运算符之后回头看发现比以前想象的好写了很多。

反正这就是道模板题。

SPFA很好卡这事大家都知道但是SPFA真是香了这么多年

#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; #define R register inline int read() { char ch=getchar(); int x=0; while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x; } struct emm{ int e,f,v; }a[200007]; int h[100007]; int n,m,s; void scan() { n=read(),m=read(),s=read(); for(R int i=1;i<=m;++i) { int u=read(),v=read(),w=read(); a[i].f=h[u]; h[u]=i; a[i].e=v; a[i].v=w; } return; } struct ahh{ int dis,cod; }aa; struct cmp{ bool operator()(ahh qaq,ahh qwq){ return qaq.dis>qwq.dis; } }; priority_queue<ahh,vector<ahh>,cmp>q; int d[100007]; bool sf[100007]; void dijkstra() { memset(d,127,sizeof(d)); d[s]=0;q.push((ahh){0,s}); while(!q.empty()) { int x; do{x=q.top().cod;q.pop();}while(sf[x]&&!q.empty()); sf[x]=1; for(R int i=h[x];i;i=a[i].f) if(d[a[i].e]>d[x]+a[i].v) { d[a[i].e]=d[x]+a[i].v; if(!sf[a[i].e])q.push((ahh){d[a[i].e],a[i].e}); } } for(R int i=1;i<=n;++i) printf("%d ",d[i]); return; } int main() { scan(); dijkstra(); return 0; }

转载于:https://www.cnblogs.com/qwerta/p/9379734.html

相关资源：找出一条从某个定点A到顶点B变数最少的一条路径

最新回复(0)

「LuoguP4779」 【模板】单源最短路径（标准版）