#P4779. P4779 【模板】单源最短路径(标准版)
P4779 【模板】单源最短路径(标准版)
P4779 【模板】单源最短路径(标准版)
普及/提高- | 来源:洛谷 | 原题链接
题意
给定 个点、 条有向带权边()与源点 。求 到每个点的最短距离,输出一行 个整数。本题为堆优化 Dijkstra 的模板题。
输入格式
第一行为三个正整数 。 第二行起 行,每行三个非负整数 ,表示从 到 有一条权值为 的有向边。
输出格式
输出一行 个空格分隔的非负整数,表示 到每个点的距离。
输入输出样例
样例 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
数据范围
,,,,,。
提示
考点:堆优化 Dijkstra 模板。易错点:① 可以为 (不能把 当无效边跳过);② 邻接表边数是 级别开够;③ 懒删除堆要在弹出时用 if (d > dist[u]) continue; 跳过过期状态。