在 520B Two Buttons 中，每次操作的代价都是 1，BFS 按层扩展就等于按距离扩展。如果一条边代价 2、另一条边代价 10，“经过的边更少”就不再等于“总代价更小”。

Codeforces 20C 把问题推进了一步：边权为正，既要算最短距离，还要输出一条真正达到该距离的路径。本文会把距离计算、贪心正确性与路径还原分开讲清楚。

1. 先读约束，再选择算法

20C · Dijkstra? 官方题目 的难度为 1900，官方标签为 graphs 和 shortest paths，于 2026-09-08 核对。题目给出无向带权图：2≤n≤100000、0≤m≤100000、边权 1≤w≤1000000，允许自环和重边，需要输出顶点 1 到顶点 n 的任意一条最短路径；不可达时输出 -1。

约束信息 直接影响
十万个点、十万条边 O(n²) 的朴素选点不可接受
边权均为正 可以使用 Dijkstra
图较稀疏 邻接表比邻接矩阵更合适
要输出顶点序列 松弛时还要记录父节点
路径和可能超过 32 位 距离必须使用 long long

最坏情况下，一条简单路径可能含 n-1 条边，距离约为 99999×1000000≈10¹¹。它远大于有符号 32 位整数上限，边权虽然能用 int，距离却不能。

2. 为什么普通 BFS 不够

考虑下面这张自拟的小图。目标是从 1 到 5；边旁数字是代价。

只按边数看，1→2→5 仅经过两条边；它的总代价却是 30。路径 1→3→2→4→5 经过四条边，总代价只有 2+3+1+2=8。

BFS 的队列保证的是“边数较少的状态先出队”。面对不同边权，我们真正需要的是“当前已知距离较小的顶点先处理”，因此把普通队列换成按距离排序的小根堆。

3. 松弛：用一条边改善一个答案

令 dist[v] 表示目前找到的从 1 到 v 的最短距离上界：

  • dist[1]=0；
  • 其他顶点初始化为无穷大；
  • 查看边 u—v、权重为 w 时，如果 dist[u]+w<dist[v]，就更新 dist[v]。

这个更新动作叫作松弛。它不是直接宣告 v 的最终答案，只是发现了一条更短的候选路径。

在上图中，顶点 2 会先由边 1—2 得到距离 10；处理顶点 3 后，又由 1→3→2 改善为 5。一个顶点被更新多次完全正常。

4. 小根堆里为什么会有过期条目

C++ 的 priority_queue 不提供直接修改堆中某个元素的 decrease-key 操作。更简单可靠的做法是：每次距离改善，就把新的 (距离, 顶点) 再压入堆中，旧记录留在里面。

以下是自拟小图前几步的关键变化；同一顶点 2 同时出现过 (10,2) 与 (5,2)：

弹出 本轮有效松弛 更新后的关键距离 堆中仍可能存在
(0,1) 1→2、1→3 d₂=10，d₃=2 (2,3)、(10,2)
(2,3) 3→2、3→4 d₂=5，d₄=10 (5,2)、(10,2)、(10,4)
(5,2) 2→4、2→5 d₄=6，d₅=25 旧的 (10,2)、(10,4)
(6,4) 4→5 d₅=8 旧的 (10,2)、(10,4)、(25,5)
(8,5) 到达目标 最短距离为 8 可以安全提前结束

弹出 (current,u) 后，若 current!=dist[u]，说明后来已经找到更短路线，这条堆记录过期，直接跳过。这个判断同时带来两个好处：避免重复扫描邻接边，也保证“弹出目标即可结束”发生在目标的有效最短距离上。

常见错误是另外维护 visited[u]，却在顶点入堆时就标记。入堆只代表发现了一个候选，像顶点 2 的距离 10 之后仍可能改成 5；过早封死会得到错误答案。

5. Dijkstra 的贪心结论为什么成立

核心不变量是：从小根堆取出的有效记录 (dist[u],u)，其距离已经是最终最短距离。

假设它仍不是最短的。沿一条真实的更短路径从起点向后走，找到第一个还没有确定最终距离的顶点 y，令它的前驱为 x。x 已经确定，因此处理 x 时一定检查过边 x—y，并得到：

dist[y] ≤ 最短距离(x) + w(x,y) = 最短距离(y)。

而距离上界不可能小于真实最短距离，所以此时 dist[y] 恰好等于真实最短距离。由于边权非负，路径上到 y 的距离不大于到 u 的距离，小根堆本应先取出 y，这与 u 是当前最小有效记录矛盾。

证明里“边权非负”不可删除。若存在负边，路径走得更远后可能再通过负边大幅降低此前顶点的距离，已确定的贪心结论会失效。20C 的边权严格为正，因此满足条件。

6. 在松弛时记录父节点

每当通过 u 改善 dist[v]，同步令 parent[v]=u。最终从 n 开始沿父节点反向走，就会得到：

n ← parent[n] ← … ← 1

将序列反转即可输出从 1 到 n 的路径。父节点必须和距离在同一次成功松弛中更新；如果只更新距离、不更新父节点，得到的顶点链与最终最短距离可能不匹配。

本题边权为正，成功松弛后父节点的距离严格更小，所以父节点链不可能形成环。遇到相同距离时不更新父节点也没问题：题目允许输出任意一条最短路径。

7. 完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

using int64 = long long;
using State = pair<int64, int>;  // 当前距离、顶点

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n + 1);
    for (int i = 0; i < m; ++i) {
        int a, b, weight;
        cin >> a >> b >> weight;
        graph[a].push_back({b, weight});
        graph[b].push_back({a, weight});
    }

    constexpr int64 INF = 4'000'000'000'000'000'000LL;
    vector<int64> dist(n + 1, INF);
    vector<int> parent(n + 1, -1);
    priority_queue<State, vector<State>, greater<State>> heap;

    dist[1] = 0;
    parent[1] = 0;
    heap.push({0, 1});

    while (!heap.empty()) {
        auto [currentDistance, u] = heap.top();
        heap.pop();
        if (currentDistance != dist[u]) continue;
        if (u == n) break;

        for (auto [v, weight] : graph[u]) {
            int64 candidate = currentDistance + weight;
            if (candidate >= dist[v]) continue;
            dist[v] = candidate;
            parent[v] = u;
            heap.push({candidate, v});
        }
    }

    if (dist[n] == INF) {
        cout << -1 << '\n';
        return 0;
    }

    vector<int> path;
    for (int v = n; v != 0; v = parent[v]) path.push_back(v);
    reverse(path.begin(), path.end());
    for (int v : path) cout << v << ' ';
    cout << '\n';
}

建无向图时要把每条边加入两个方向。自环会被加入两次，但正权自环不可能改善距离；重边会分别参与松弛，较轻或能形成更短路径的那条自然胜出，无需预先去重。

使用允许重复记录的二叉堆时，堆中最多有 O(m) 个条目，严格写法是时间 O((n+m)log m)；在通常的简单图分析中，也常写作 O((n+m)log n)。邻接表、距离、父节点与堆的总体空间为 O(n+m)。

8. 边界与故障清单

情况 正确行为 容易犯的错误
m=0 顶点 n 不可达，输出 -1 强行回溯未初始化父节点
只有一条直达边 输出 1 n 输出距离而非路径
存在重边 保留所有边也能正确松弛 误以为输入一定是简单图
存在自环 正权下不会改善自身 无意义地反复入堆
多条等长最短路 输出任意一条 为追求唯一答案增加错误限制
路径和超过 2³¹-1 用 long long 保存距离与堆键 只把 INF 改大，dist 仍用 int
堆中存在旧距离 与当前 dist[u] 比较后跳过 把第一次入堆误当作最终确定

INF 要明显大于最大可能答案，同时给加法留出余量。这里最大的合法简单路径远小于 4×10¹⁸，而我们只对从堆中取出的有限距离做加法，因此不会计算 INF+weight。

9. 怎样做独立验证

手工样例只能检查一条路径。更可靠的做法是在小图上随机生成正权边，用 O(n³) 的 Floyd–Warshall 独立算出最短距离，再验证程序输出：

  1. 不可达时是否恰好输出 -1；
  2. 路径是否从 1 开始、在 n 结束；
  3. 每对相邻顶点之间是否存在输入边；
  4. 路径总权重是否等于独立算法的最短距离。

还应专门构造重边、自环、孤立终点和超过 32 位的长链。验证程序应检查输出路径本身，而不只是比较一个距离，因为 20C 的输出目标正是一条路径。

完成这题后，可以修改条件继续推演：所有边权都等于 1 时退化为 BFS；边权只有 0 和 1 时可以使用双端队列实现 0-1 BFS；出现负边时则不能继续套 Dijkstra。回到 算法练习路径 时，应把“边权是什么”放在选择最短路算法之前。