Dijkastra(II)

GitHub跳转原题关系图返回列表

无向连通图求 1 到 n 的最短路:链式前向星存双向边,小根堆优化 Dijkstra 出堆即定稿,距离用 long long 扛住 2e14 量级。

OJ: roj

题目 ID: 1420

难度:普及+/提高-

标签:图论最短路Dijkstra堆python

创建: 2026-10-07 15:11

更新: 2026-10-07 15:11

形式化题目

给定一张 NN 个点、MM 条边的无向连通带权图,每条边形如 (s,t,d)(s, t, d), 表示点 ss 与点 tt 之间有一条长度为 dd 的边,其中 1⩽s,t⩽N1 \leqslant s, t \leqslant N、 0⩽d⩽1090 \leqslant d \leqslant 10^9。边可以重复出现(重边),也可以两端相同(自环), 并且图保证从点 11 出发可以到达点 nn。

求从点 11 到点 nn 的所有路径中,边权总和的最小值,输出这个整数。

正解

思路

先确认算法。 边权满足 d⩾0d \geqslant 0,这是 Dijkstra 能用的前提:它基于"距离小的点一旦定稿就不会再被更短的路径改写"这一贪心性质,只要没有负权边,性质就成立。图是无向的、连通性有保证,所以 1→n1 \to n 一定可达,不需要处理不可达的输出约定。

暴力瓶颈在哪? 如果不借助任何数据结构、每轮线性扫描所有未定稿点找最小(即朴素 O(N2)O(N^2) Dijkstra),N=2×105N = 2\times10^5 时是 4×10104\times10^{10} 次比较; 如果退回 Bellman–Ford 的 NN 轮全边松弛,则是 O(NM)=8×1010O(NM) = 8\times10^{10},两者都必然超时。 瓶颈是"每轮都在重复检查已经定稿的点",而真正有效的只有"当前距离最小的那个未定稿点"。

用堆把"取最小"变成 O(log⁡)O(\log)。 把候选状态 (dis,u)(dis, u) 放进小根堆,每次取出全局距离最小的点定稿。这个点不可能再被改善:任何通往它的其它路径都要先经过某个距离更大的未定稿点,加上非负边权只会更长。定稿后用它松弛所有出边,被改善的邻居才重新入堆。整体复杂度 O((N+M)log⁡N)O((N+M) \log N),顶格数据下不到 100 ms。

三个必须处理的细节。

细节 处理方式 不处理的后果
重边 正反各挂一条边即可,Dijkstra 的"取更小值"天然把重边当多条候选 需要额外判重,代码更长
自环 s == t 时直接跳过(样例里就有 2 2 0) 不影响正确性,但白占一次松弛
距离溢出 dis 用 64 位;最长路径可达 2×105×109=2×10142 \times 10^5 \times 10^9 = 2 \times 10^{14} 用 int 溢出,大权值数据直接算错

第三点是本题真正的卡点。理论上界:N=2×105N = 2\times10^5 的链上每条边权都取 10910^9 时, 路径和可达 199999×109≈2×1014199999 \times 10^9 \approx 2 \times 10^{14},远超 32 位整数上限 231−1≈2.1×1092^{31}-1 \approx 2.1 \times 10^9。真实数据也把这一点做进去了:第 5 点答案 24724450012472445001、第 8 点答案 26287474800802≈2.6×101326287474800802 \approx 2.6 \times 10^{13}、 第 9 点答案 30710715303071071530,三者都超过 231−12^{31}-1。把 dis 改成 32 位再跑, 这三点会直接输出错误结果(其余点仍对),是很好的自检手段。

为什么堆里可以有同一个点的多个堆项? 标准 priority_queue 不支持 decrease-key,所以"距离变小"只能再压一个新堆项。代价是堆里出现过期项, 用"已定稿"标记(C++ 的 done[u]、Python 的 settled[u])来跳过: 每个点只被定稿一次,每条边只从定稿点出发松弛一次, 所以总时间仍是 O((N+M)log⁡N)O((N+M)\log N),只是常数略大。

下面对题目样例(N=2N=2,三条边 (1,2,1)(1,2,1)、(1,2,3)(1,2,3)、(2,2,0)(2,2,0))逐轮追踪:

步骤 出堆的 (dis,u)(dis, u) 定稿 堆中剩余 dis 数组
初始 — — (0,1)(0,1) dis=[0,∞]dis = [0, \infty]
1 (0,1)(0, 1) 1 (1,2)(1,2) dis=[0,1]dis = [0, 1]
2 (1,2)(1, 2) 2 空 dis=[0,1]dis = [0, 1]

这张表说明了重边与自环为什么都不用特判。第一步从点 1 出发时有两条通往点 2 的边: w=1w=1 的让 dis[2]dis[2] 从 ∞\infty 降到 11 并入堆,w=3w=3 的算出 0+3=30+3=3 不小于已有的 11, 直接被松弛条件挡掉——重边只是多条候选路径,先到的那条自然占优; 自环 (2,2,0)(2,2,0) 在松弛时算出 dis[2]+0=1dis[2]+0=1,不小于 dis[2]=1dis[2]=1,同样天然被过滤, 所以读入时跳过它只是为了省一次无用操作,不是正确性必需。第二步取出 (1,2)(1,2) 时 u=nu = n,点 nn 已定稿,答案直接返回。

过期堆项要用一个稍大一点的例子才看得出来:N=4N=4,边为 (1,2,10)(1,2,10)、(1,3,1)(1,3,1)、 (3,2,1)(3,2,1)、(3,4,20)(3,4,20)。

步骤 出堆的 (dis,u)(dis, u) 定稿 堆中剩余 dis 数组
初始 — — (0,1)(0,1) dis=[0,∞,∞,∞]dis = [0, \infty, \infty, \infty]
1 (0,1)(0, 1) 1 (1,3), (10,2)(1,3),\ (10,2) dis=[0,10,1,∞]dis = [0, 10, 1, \infty]
2 (1,3)(1, 3) 3 (2,2), (10,2), (21,4)(2,2),\ (10,2),\ (21,4) dis=[0,2,1,21]dis = [0, 2, 1, 21]
3 (2,2)(2, 2) 2 (10,2), (21,4)(10,2),\ (21,4) dis=[0,2,1,21]dis = [0, 2, 1, 21]
4 (10,2)(10, 2) 跳过(已定稿) (21,4)(21,4) 不变
5 (21,4)(21, 4) 4 空 dis=[0,2,1,21]dis = [0, 2, 1, 21]

关键是第 1 步压入的 (10,2)(10,2) 在第 2 步之后就成了过期堆项:点 2 的真实距离已被 1→3→21 \to 3 \to 2 改写成 22,但 (10,2)(10,2) 仍留在堆里。第 4 步取出它时被"已定稿"标记直接跳过。 这正是"堆优化 + 惰性删除"的全部分量:不支持 decrease-key 就用标记筛掉旧项, 每个点仍只被定稿一次,复杂度不变。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:每个点定稿一次,每次定稿松弛它的全部出边,所以总松弛次数为 O(N+M)O(N + M); 每次入堆/出堆 O(log⁡N)O(\log N),合计 O((N+M)log⁡N)O((N + M)\log N)。顶格 N=2×105N = 2\times10^5、 M=4×105M = 4\times10^5 时实测 C++ 约 50–80 ms(限时 1000 ms), Python 最慢的第 9 点约 0.5–0.6 s。
  • 空间:C++ 的链式前向星按 2M2M 条有向边存 to / nxt / wt 三个数组, 加上 head / dis / done,总计 O(N+M)O(N + M),实测峰值 21 MB。 Python 把邻接边打包成整数存进 array('q'),峰值约 55–57 MB(限制 128 MB)。
  • 与 Python 解法的关系:main.py 是同一算法的 Python 版本, 两处为内存让步:一是把邻接边和堆元素都打包成一个整数(低位放点号、高位放距离), 用 array('q') 替代 Python 列表,避开 8×1058\times10^5 个元组对象; 二是分词逐行惰性取值而不是 read().split()(后者实测峰值 129 MB,已超限制)。 算法与复杂度同阶,只是常数与内存布局不同。

总结

  • 先看边权定算法:d⩾0d \geqslant 0 才允许 Dijkstra;只要有一条负边,本题就要换成 SPFA 或 Bellman–Ford。同一题面系列的 1419【SPFA(II)】正是这个图模型下的另一条路线。
  • 堆优化消灭的是"取最小"这一步:把 O(N)O(N) 的线性找最小换成 O(log⁡N)O(\log N) 的堆操作, 于是朴素 O(N2)O(N^2) Dijkstra 被压到 O((N+M)log⁡N)O((N+M)\log N)。
  • 不支持 decrease-key 就惰性删除:允许同一压入多个堆项,用"已定稿"标记跳过过期项, 这是所有竞赛版堆优化 Dijkstra 的通用写法,复杂度不受影响。
  • 重边与自环不用特判:重边就是多条候选路径,自环的松弛不等式天然不成立; 读入时跳过自环纯粹是为了省一次无用操作。
  • 距离类型要看路径长度上界:2×1052\times10^5 个 10910^9 边相加已经到 2×10142\times10^{14}, 32 位装不下。把 dis 换成 int 重跑一遍,第 5、8、9 三个点会当场算错, 这是本题唯一容易丢分的地方。