#P4779. P4779 【模板】单源最短路径(标准版)

P4779 【模板】单源最短路径(标准版)

P4779 【模板】单源最短路径(标准版)

普及/提高- | 来源:洛谷 | 原题链接

题意

给定 nn 个点、mm 条有向带权边(wi≥0w_i \ge 0)与源点 ss。求 ss 到每个点的最短距离,输出一行 nn 个整数。本题为堆优化 Dijkstra 的模板题。

输入格式

第一行为三个正整数 n,m,sn, m, s。 第二行起 mm 行,每行三个非负整数 ui,vi,wiu_i, v_i, w_i,表示从 uiu_i 到 viv_i 有一条权值为 wiw_i 的有向边。

输出格式

输出一行 nn 个空格分隔的非负整数,表示 ss 到每个点的距离。

输入输出样例

样例 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

数据范围

1≤n≤1051\le n\le 10^5,1≤m≤2×1051\le m\le 2\times10^5,s=1s=1,1≤ui,vi≤n1\le u_i,v_i\le n,0≤wi≤1090\le w_i\le 10^9,0≤∑wi≤1090\le \sum w_i\le 10^9。

提示

考点:堆优化 Dijkstra 模板。易错点:① ww 可以为 00(不能把 w=0w=0 当无效边跳过);② 邻接表边数是 2m2m 级别开够;③ 懒删除堆要在弹出时用 if (d > dist[u]) continue; 跳过过期状态。

蜀ICP备2025119001号-1