20C Dijkstra 解决了“从一个起点到其他顶点的最短距离与路径还原”。但真实题目常把最短距离当作第一层约束，再追问另一个问题：在所有最短路中怎样选最轻的树，哪些特殊边可以删，或者每个点应该选择哪个终点。

本文用三道 Codeforces 题把 Dijkstra 从“套模板”推进到“改模型”。545E 在距离相同的前驱中选最轻入边；449B 判断列车边是否真是某个城市维持最短距离所必需；938D 则把所有票价同时作为初始距离，运行一次多源 Dijkstra。

1. 官方资料与学习路线

题名、难度、标签和约束于 2026-09-23 通过 Codeforces 官方题目页核对。

题目 官方难度 官方标签 关键约束 本文训练点
545E Paths and Trees 2000 graphs、greedy、shortest paths n,m ≤ 3×10^5，边权 ≤10^9 最短距离固定后独立选择最轻父边
449B Jzzhu and Cities 2000 graphs、greedy、shortest paths n,k≤10^5，m≤3×10^5 区分严格改善与等距替代，最大化删边数
938D Buy a Ticket 2000 data structures、graphs、shortest paths n,m≤2×10^5，费用 ≤10^12 虚拟源点、多源 Dijkstra、边权翻倍

三题都使用非负边权和小根堆，但堆外维护的状态不同。先写清“相等距离时究竟要做什么”，比背诵松弛代码更重要。

2. 共同基础：Dijkstra 只承诺距离

标准松弛比较：

1
newDistance = distance[u] + weight(u,v)

若 newDistance < distance[v]，显然应更新；若两者相等，标准距离问题可以什么都不做，但本文三题的附加目标恰恰藏在等号里。

情况 距离数组怎样变 附加信息可能怎样变
新距离更短 覆盖 dist[v] 旧父边、旧来源通常失效
新距离相等 不改变 dist[v] 可换更轻父边，或证明特殊边冗余
新距离更长 不处理 不可能改善距离或等距结构

正权边还有一个重要性质：若 u 是 v 的最短路前驱，则 dist[u] < dist[v]。沿父边回溯时距离严格下降，因此不会形成环。这将使 545E 的局部选择自动拼成一棵树。

3. 第一题：545E Paths and Trees

3.1 两层目标不能混成一个权值

题目先要求从源点到每个顶点的距离仍等于原图最短距离，再要求所选 n-1 条树边的总权值最小。

不能把路径长度和树边总重随手组合成 distance × C + edgeWeight 再跑一次 Dijkstra：一条树边会被多个根到点路径共享，而“路径代价”和“整棵树的边权和”不是同一个可加目标。

正确拆法是：

  1. Dijkstra 确定每个点的最短距离 dist[v]。
  2. 对每个非源点 v，从所有满足 dist[u]+w=dist[v] 的入边中选择权值最小的一条。

3.2 为什么每个点可以独立选父边

所有候选父边都保持 v 的最短距离。由于边权严格为正，候选父节点 u 的距离严格小于 v。所以每个点各选一条候选边后：

  • 沿父边距离严格下降，绝不可能成环；
  • 每个非源点恰有一条父边；
  • 连续回溯最终只能到源点；
  • 每条根到点路径仍是最短路。

树边总重就是各非源点父边权之和。各点的选择之间没有冲突，因此分别取最轻候选边即可得到全局最小和。

3.3 手工例子

源点是 1，有边 1-2(2)、1-3(3)、2-3(1)、2-4(5)、3-4(4)。

顶点 最短距离 可选最短路父边 选择
2 2 1-2(2) 权 2
3 3 1-3(3)、2-3(1) 权 1
4 7 2-4(5)、3-4(4) 权 4

到 3 的两条路径长度同为 3，但选 2-3 能让树边总重少 2。到 4 同理。最终总重为 2+1+4=7。

3.4 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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

struct Edge {
    int to;
    long long weight;
    int index;
};

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

    int n, m;
    cin >> n >> m;
    vector<vector<Edge>> graph(n);
    for (int index = 1; index <= m; ++index) {
        int u, v;
        long long weight;
        cin >> u >> v >> weight;
        --u;
        --v;
        graph[u].push_back({v, weight, index});
        graph[v].push_back({u, weight, index});
    }
    int source;
    cin >> source;
    --source;

    const long long infinity = numeric_limits<long long>::max() / 4;
    vector<long long> distance(n, infinity);
    vector<long long> parentWeight(n, infinity);
    vector<int> parentEdge(n, -1);
    priority_queue<pair<long long, int>,
                   vector<pair<long long, int>>,
                   greater<pair<long long, int>>> heap;

    distance[source] = 0;
    heap.push({0, source});
    while (!heap.empty()) {
        const auto [currentDistance, vertex] = heap.top();
        heap.pop();
        if (currentDistance != distance[vertex]) {
            continue;
        }
        for (const Edge& edge : graph[vertex]) {
            const long long candidate = currentDistance + edge.weight;
            if (candidate < distance[edge.to]) {
                distance[edge.to] = candidate;
                parentWeight[edge.to] = edge.weight;
                parentEdge[edge.to] = edge.index;
                heap.push({candidate, edge.to});
            } else if (candidate == distance[edge.to]
                       && edge.weight < parentWeight[edge.to]) {
                parentWeight[edge.to] = edge.weight;
                parentEdge[edge.to] = edge.index;
            }
        }
    }

    long long totalWeight = 0;
    for (int vertex = 0; vertex < n; ++vertex) {
        if (vertex != source) {
            totalWeight += parentWeight[vertex];
        }
    }
    cout << totalWeight << '\n';
    for (int vertex = 0; vertex < n; ++vertex) {
        if (vertex != source) {
            cout << parentEdge[vertex] << ' ';
        }
    }
    cout << '\n';
    return 0;
}

复杂度为 O((n+m) log n)，空间复杂度 O(n+m)。总边权可能超过 32 位整数。

4. 第二题：449B Jzzhu and Cities

4.1 最大删除数等于最少保留数

有普通双向道路，也有从首都 1 直达某城市的列车。要求删除尽量多的列车，同时保持所有城市到首都的最短距离不变。

把每条列车看成从源点发出的特殊边，就能与普通道路一起计算距离。但不能只问“这条列车是否等于最短距离”，因为同一城市可能有多条同价列车，也可能存在同长的纯道路路径。

4.2 什么时候一条列车必须保留

一个城市最多需要保留一条列车。它必须同时满足：

  1. 它给出了该城市的最短初值；
  2. 没有普通道路能以相同或更短距离到达该城市。

初始化时，每个城市只记录最便宜的列车距离，其他同城列车先视为冗余。Dijkstra 扫描普通道路：

  • 若道路给出更短距离，原列车不再需要；
  • 若道路给出相等距离，也可用道路替代列车，原列车同样不需要；
  • 只有最终仍标记为“由列车独占”的城市，需要保留一条列车。

答案为 k - 必需列车数。

4.3 为什么等距道路足以删列车

设道路 u-v 满足 dist[u]+w=dist[v]。边权为正，所以 dist[u]<dist[v]。沿着这样的道路前驱不断回溯，距离严格下降，不会形成循环，最终会到达首都，或到达另一个确实需要列车的城市。

因此当 v 存在等距道路前驱时，不必为 v 单独保留列车；即使这条替代路径的更早部分使用了某条列车，也只需保留那个更靠近距离起点的必要来源。

情况 同城列车是否保留
有更便宜列车 较贵列车全部删除
有同价多条列车 最多保留一条
普通道路给出更短路径 全部删除
普通道路给出等长路径 全部删除
列车严格优于所有道路路径 保留最便宜的一条

4.4 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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

struct Road {
    int to;
    long long length;
};

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

    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<Road>> graph(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long length;
        cin >> u >> v >> length;
        --u;
        --v;
        graph[u].push_back({v, length});
        graph[v].push_back({u, length});
    }

    const long long infinity = numeric_limits<long long>::max() / 4;
    vector<long long> distance(n, infinity);
    vector<bool> needsTrain(n, false);
    priority_queue<pair<long long, int>,
                   vector<pair<long long, int>>,
                   greater<pair<long long, int>>> heap;
    distance[0] = 0;
    heap.push({0, 0});

    for (int i = 0; i < k; ++i) {
        int city;
        long long length;
        cin >> city >> length;
        --city;
        if (length < distance[city]) {
            distance[city] = length;
            needsTrain[city] = true;
            heap.push({length, city});
        }
    }

    while (!heap.empty()) {
        const auto [currentDistance, vertex] = heap.top();
        heap.pop();
        if (currentDistance != distance[vertex]) {
            continue;
        }
        for (const Road& road : graph[vertex]) {
            const long long candidate = currentDistance + road.length;
            if (candidate < distance[road.to]) {
                distance[road.to] = candidate;
                needsTrain[road.to] = false;
                heap.push({candidate, road.to});
            } else if (candidate == distance[road.to]) {
                needsTrain[road.to] = false;
            }
        }
    }

    int kept = 0;
    for (bool needed : needsTrain) {
        kept += needed ? 1 : 0;
    }
    cout << k - kept << '\n';
    return 0;
}

复杂度为 O((n+m+k) log n)，空间复杂度 O(n+m)。

5. 第三题：938D Buy a Ticket

5.1 原式先暴露两个结构

从城市 i 去城市 j 看演出再返回，代价是：

1
ticket[j] + 2 × shortestDistance(i,j)

对每个 i 枚举所有 j，即使已经得到任意两点距离也太贵。先做两步等价变换：

  1. 把每条道路权值 w 改成 2w，往返就变成新图中的单程距离。
  2. 给每个城市 j 一个初始距离 ticket[j]，让所有城市同时作为源点传播。

最终 dist[i] 正是所有 ticket[j] + 2d(i,j) 的最小值。

5.2 虚拟源点解释

可以新增虚拟源点 S，向每个城市 j 连一条权为 ticket[j] 的边，原道路权值翻倍。从 S 到 i 的任意路径先选择一条票价边，再沿道路抵达 i：

1
2
S → j → ... → i
代价 = ticket[j] + 2 × roadDistance(j,i)

把 dist[j]=ticket[j] 全部压入堆，与显式创建虚拟源点完全等价，却少一个顶点和 n 条实际存储的边。

5.3 手工演算

三个城市道路为 1-2(1)、2-3(1)，票价 [30,10,20]。翻倍后的道路权为 2。

城市 留在本城 去城市 2 买票 其他选择 最优
1 30 10+2=12 去 3 为 24 12
2 10 10 去 3 为 22 10
3 20 10+2=12 去 1 为 34 12

多源 Dijkstra 的初始堆中同时有 (30,1)、(10,2)、(20,3)。城市 2 的低票价向两边扩散，一次运行就得到 [12,10,12]。

5.4 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
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

struct Edge {
    int to;
    long long doubledCost;
};

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

    int n, m;
    cin >> n >> m;
    vector<vector<Edge>> graph(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long cost;
        cin >> u >> v >> cost;
        --u;
        --v;
        graph[u].push_back({v, 2 * cost});
        graph[v].push_back({u, 2 * cost});
    }

    vector<long long> distance(n);
    priority_queue<pair<long long, int>,
                   vector<pair<long long, int>>,
                   greater<pair<long long, int>>> heap;
    for (int city = 0; city < n; ++city) {
        cin >> distance[city];
        heap.push({distance[city], city});
    }

    while (!heap.empty()) {
        const auto [currentDistance, vertex] = heap.top();
        heap.pop();
        if (currentDistance != distance[vertex]) {
            continue;
        }
        for (const Edge& edge : graph[vertex]) {
            const long long candidate = currentDistance + edge.doubledCost;
            if (candidate < distance[edge.to]) {
                distance[edge.to] = candidate;
                heap.push({candidate, edge.to});
            }
        }
    }

    for (int city = 0; city < n; ++city) {
        cout << distance[city] << (city + 1 == n ? '\n' : ' ');
    }
    return 0;
}

复杂度为 O((n+m) log n)，空间复杂度 O(n+m)。道路费用、票价和路径和均须使用 long long。

6. 三种“额外来源”不要混淆

题目 初始源点 等距时的动作 最终输出
545E 一个给定源点 比较最后一条父边的权值 最轻最短路树的边
449B 首都与若干列车初值 普通道路等距即可淘汰该城列车 最大可删除列车数
938D 每个城市都是带票价的源点 无额外选择，普通距离最小化即可 每个城市的最小总费用

545E 的父边权不是第二维路径代价；449B 的列车标记不是“这条最短路是否曾从列车开始”；938D 也不是从每个点分别跑 Dijkstra。先明确状态含义，代码才不会因为形式相似而混用。

7. 正确性总结

545E

Dijkstra 给出唯一的最短距离标号。每个非源点从所有满足最短路等式的边中独立选择最轻者；正权保证父节点距离严格更小，所有选择无环且连向源点。任意合法最短路树都必须为每个非源点选择一条这样的边，因此逐点最小使总和最小。

449B

初始化保留每城最短列车候选。若普通道路严格改善或等距到达该城，则存在无需该城列车的同长方案；正权使等距道路前驱沿距离严格下降，替代关系不会成环。最终仍标记的城市没有道路等距前驱，每城至少要留一条列车，故保留数最小、删除数最大。

938D

虚拟源点到城市 j 的边权是票价，原道路权翻倍。虚拟源点到 i 的每条路径一一对应“在某城买票并往返”的方案，路径权正好等于方案费用；反之每个方案都能构成这种路径。因此单源最短路等于所求最小费用，多源初始化只是省略显式虚拟源点。

8. 边界与错误清单

  1. 545E 在等距时比较整条路径。 距离已经相等，附加目标只需比较进入当前点的父边权。
  2. 545E 认为逐点选父边可能成环。 本题边权至少为 1，父边使距离严格下降。
  3. 545E 忘记 n=1。 总权为 0，边列表为空。
  4. 449B 为每条列车建图后只统计未用边。 Dijkstra 选中的某一条前驱不代表其他等距方案不存在。
  5. 449B 只在道路严格更短时删列车。 等距道路同样能保持所有距离。
  6. 449B 同城同价列车全部保留。 最多只可能需要一条。
  7. 938D 从每个城市分别运行 Dijkstra。 会从近线性复杂度退化到无法接受。
  8. 938D 忘记往返使道路费用乘 2。 票价不乘 2。
  9. 三题继续使用 int 存距离。 费用与长路径远超 32 位范围。
  10. 处理堆中过期条目时只比较访问标记。 距离可能被多次改善，直接判断堆中距离是否等于当前 dist 更清楚。

9. 独立验证

tests/verify-shortest-paths-three-article.cjs 会提取并无警告编译三份 C++17 代码，再用不同方法验证：

  • 545E 使用 Bellman–Ford 式全边松弛得到距离，逐点枚举所有合法父边的最小权，并检查程序输出确实构成树；
  • 449B 枚举所有列车保留子集，重新计算距离，直接寻找最少保留数；
  • 938D 用 Floyd–Warshall 求小图任意两点距离，再枚举买票城市。

随机数据覆盖等距路径、同城重复列车、重边、非连通道路分量与大权值；规模测试覆盖三题官方最大 n，同时检查超过 32 位的结果。

10. 下一步

读完后可以对照 1245D 电网规划：那里同样加入虚拟源点，但目标是最小生成树，而 938D 是最短路。两者都把“特殊选择”转成普通边，却分别依赖割性质与路径松弛；能分清这两个模型，才算真正掌握虚拟点，而不是看到额外选项就机械建边。