无向连通图求 1 到 n 的最短路:链式前向星存双向边,小根堆优化 Dijkstra 出堆即定稿,距离用 long long 扛住 2e14 量级。
OJ: roj
题目 ID: 1420
难度:普及+/提高-
标签:图论最短路Dijkstra堆python
创建: 2026-10-07 15:11
更新: 2026-10-07 15:11
形式化题目
给定一张
求从点
正解
思路
先确认算法。 边权满足
暴力瓶颈在哪? 如果不借助任何数据结构、每轮线性扫描所有未定稿点找最小(即朴素
用堆把"取最小"变成
三个必须处理的细节。
| 细节 | 处理方式 | 不处理的后果 |
|---|---|---|
| 重边 | 正反各挂一条边即可,Dijkstra 的"取更小值"天然把重边当多条候选 | 需要额外判重,代码更长 |
| 自环 | s == t 时直接跳过(样例里就有 2 2 0) |
不影响正确性,但白占一次松弛 |
| 距离溢出 | dis 用 64 位;最长路径可达 |
用 int 溢出,大权值数据直接算错 |
第三点是本题真正的卡点。理论上界:dis 改成 32 位再跑,
这三点会直接输出错误结果(其余点仍对),是很好的自检手段。
为什么堆里可以有同一个点的多个堆项? 标准 priority_queue 不支持
decrease-key,所以"距离变小"只能再压一个新堆项。代价是堆里出现过期项,
用"已定稿"标记(C++ 的 done[u]、Python 的 settled[u])来跳过:
每个点只被定稿一次,每条边只从定稿点出发松弛一次,
所以总时间仍是
下面对题目样例(
| 步骤 | 出堆的 |
定稿 | 堆中剩余 | dis 数组 |
|---|---|---|---|---|
| 初始 | — | — | ||
| 1 | 1 | |||
| 2 | 2 | 空 |
这张表说明了重边与自环为什么都不用特判。第一步从点 1 出发时有两条通往点 2 的边:
过期堆项要用一个稍大一点的例子才看得出来:
| 步骤 | 出堆的 |
定稿 | 堆中剩余 | dis 数组 |
|---|---|---|---|---|
| 初始 | — | — | ||
| 1 | 1 | |||
| 2 | 3 | |||
| 3 | 2 | |||
| 4 | 跳过(已定稿) | 不变 | ||
| 5 | 4 | 空 |
关键是第 1 步压入的
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:11
# update_at: 2026-10-07 15:11
import sys
from array import array
from collections.abc import Iterator
from heapq import heappop, heappush
INF = 1 << 60 # 距离哨兵:本题最长的最短路也不超过 2e5 * 1e9 = 2e14
SHIFT = 20 # 打包用:低 20 位专放点号(N ≤ 2e5 < 2^20),高位放距离
ID_MASK = (1 << SHIFT) - 1
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Adj = list[array] # 邻接表:adj[u] 是点 u 的「打包边」数组,一条边一个 8 字节整数
def read_graph(tokens: Iterator[int], n: int, m: int) -> Adj:
"""按题面格式读入 m 条无向边,建成邻接表 adj[1..n]。"""
adj: Adj = [array('q') for _ in range(n + 1)]
for _ in range(m):
s, t, d = next(tokens), next(tokens), next(tokens)
if s == t:
continue # 自环对最短路没有贡献(样例里就有 2 2 0)
adj[s].append((d << SHIFT) | t) # 无向边:正反各挂一次
adj[t].append((d << SHIFT) | s)
return adj
def shortest_path(adj: Adj, n: int) -> int:
"""堆优化 Dijkstra:回答「点 1 到点 n 的最短距离是多少」。
堆里把 (距离, 点号) 打包成一个整数,低位留给点号,于是整数序就是距离序,
省掉元组比较,也省掉元组的额外内存。每个点只在第一次出堆时定稿,
同一个点的过期堆项直接跳过,因此不需要 decrease-key;点 n 定稿即可返回。
"""
dis = [INF] * (n + 1) # dis[u] 是当前已知的 1 到 u 的最短距离
dis[1] = 0
settled = bytearray(n + 1) # settled[u] = 1 表示 u 的距离已经定稿
heap = [1] # 源点:距离 0、点号 1
while heap:
item = heappop(heap)
u = item & ID_MASK
if settled[u]:
continue # 过期堆项:u 已经用更短的距离定稿过
settled[u] = 1
d = item >> SHIFT
if u == n:
return d # 点 n 定稿,堆里剩下的距离都不可能更小
for edge in adj[u]:
v = edge & ID_MASK
nd = d + (edge >> SHIFT) # 先经 u、再走这条边到 v 的距离
if nd < dis[v]:
dis[v] = nd
candidate = (nd << SHIFT) | v # 把新的 (距离, 点号) 压回堆
heappush(heap, candidate)
return dis[n] # 图保证连通,这里只是兜底
def solve() -> None:
"""读入图、调用 Dijkstra、输出 1 到 n 的最短距离。"""
# 分词这一层逐行 readline 惰性产出,取值仍然一律走 next() 顺序消费(见 read_graph)。
# 不用 read().split():本题输入最大 9MB,一次性读会把上百万个 bytes 对象同时留在
# 内存里(实测峰值 129MB,已超 128MB 限制),逐行读取只要 55MB。
tokens = (int(t) for line in iter(sys.stdin.buffer.readline, b"") for t in line.split())
n, m = next(tokens), next(tokens)
print(shortest_path(read_graph(tokens, n, m), n))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 15:11
* update_at: 2026-10-07 15:11
*/
// main.cpp:一本通 1420《Dijkastra(II)》,无向连通图求点 1 到点 n 的最短路。
// 与 main.py 同一算法:链式前向星存图 + 小根堆优化的 Dijkstra。
// 边权 0 ≤ d ≤ 1e9,最长路径可达约 2e5 * 1e9 = 2e14,距离必须用 long long。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005; // N ≤ 200000
const int MAXM = 400005; // M ≤ 400000
const ll INF = 4000000000000000000LL; // 比任何可能的最短路(约 2e14)都大得多
int n, m; // 点数、边数
int head[MAXN]; // head[u]:点 u 的第一条出边编号,0 表示没有出边
int to[2 * MAXM]; // to[e]:第 e 条边的终点
int nxt[2 * MAXM]; // nxt[e]:同一个起点的下一条边编号
int wt[2 * MAXM]; // wt[e]:边权,0 ≤ d ≤ 1e9,用 int 存足够
int edge_cnt; // 已经加入的边数(无向边要加两条)
ll dis[MAXN]; // dis[u]:当前已知的 1 到 u 的最短距离
bool done[MAXN]; // done[u]:u 是否已经出堆定稿
// 加一条有向边 u -> v,权值为 d。
void add_edge(int u, int v, int d) {
edge_cnt++;
to[edge_cnt] = v;
wt[edge_cnt] = d;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void read_input() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int s, t, d;
cin >> s >> t >> d;
if (s == t) continue; // 自环对最短路没有任何贡献(样例里就有 2 2 0)
add_edge(s, t, d); // 无向边:正反各加一条
add_edge(t, s, d);
}
}
// 堆优化 Dijkstra:每个点只在第一次出堆时定稿,输出 dis[n]。
void solve() {
for (int i = 1; i <= n; i++) dis[i] = INF;
dis[1] = 0;
// 小根堆,元素是 pair<距离, 点号>,距离小的先出堆
priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > heap;
heap.push(make_pair(0LL, 1));
while (!heap.empty()) {
pair<ll, int> top = heap.top();
heap.pop();
int u = top.second;
if (done[u]) continue; // 同一个点的旧距离可能被压入多次,只认第一次
done[u] = true;
if (u == n) break; // 点 n 已经定稿,后面的堆项不可能让答案更小
for (int e = head[u]; e != 0; e = nxt[e]) {
int v = to[e];
if (!done[v] && dis[u] + wt[e] < dis[v]) { // 松弛成功才入堆
dis[v] = dis[u] + wt[e];
heap.push(make_pair(dis[v], v));
}
}
}
cout << dis[n] << "\n"; // 图保证连通,dis[n] 一定可达
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
- 时间:每个点定稿一次,每次定稿松弛它的全部出边,所以总松弛次数为
; 每次入堆/出堆 ,合计 。顶格 、 时实测 C++ 约 50–80 ms(限时 1000 ms), Python 最慢的第 9 点约 0.5–0.6 s。 - 空间:C++ 的链式前向星按
条有向边存 to / nxt / wt三个数组, 加上head / dis / done,总计,实测峰值 21 MB。 Python 把邻接边打包成整数存进 array('q'),峰值约 55–57 MB(限制 128 MB)。 - 与 Python 解法的关系:
main.py是同一算法的 Python 版本, 两处为内存让步:一是把邻接边和堆元素都打包成一个整数(低位放点号、高位放距离), 用array('q')替代 Python 列表,避开个元组对象; 二是分词逐行惰性取值而不是 read().split()(后者实测峰值 129 MB,已超限制)。 算法与复杂度同阶,只是常数与内存布局不同。
总结
- 先看边权定算法:
才允许 Dijkstra;只要有一条负边,本题就要换成 SPFA 或 Bellman–Ford。同一题面系列的 1419【SPFA(II)】正是这个图模型下的另一条路线。 - 堆优化消灭的是"取最小"这一步:把
的线性找最小换成 的堆操作, 于是朴素 Dijkstra 被压到 。 - 不支持 decrease-key 就惰性删除:允许同一压入多个堆项,用"已定稿"标记跳过过期项, 这是所有竞赛版堆优化 Dijkstra 的通用写法,复杂度不受影响。
- 重边与自环不用特判:重边就是多条候选路径,自环的松弛不等式天然不成立; 读入时跳过自环纯粹是为了省一次无用操作。
- 距离类型要看路径长度上界:
个 边相加已经到 , 32 位装不下。把 dis换成int重跑一遍,第 5、8、9 三个点会当场算错, 这是本题唯一容易丢分的地方。