「一本通 3.2 练习 7」道路和航线

形式化题目

给定一张有 $T$ 个点的有向/无向混合图，边分两类：

道路：无向边，边权 $0 \leqslant C_i \leqslant 10^4$ ；
航线：有向边 $A_i \to B_i$ ，边权 $-10^4 \leqslant C_i \leqslant 10^4$ 。

额外保证：对任意航线 $A \to B$ ，不存在一条由道路与航线组成的、从 $B$ 回到 $A$ 的路径（即图中无环可归因于航线）。求起点 $S$ 到所有点的单源最短路；不可达的点报告不存在路径。

这一保证用「道路连通块」的语言可以改写为：把每个道路连通块收缩成一个超级点后，所有跨块航线构成的图是一张有向无环图。

暴力解法

思路

图中有负权边，最直接的单源最短路做法是 Bellman-Ford：

text

1
2
3
4dist[S] = 0，其余为 INF
重复 T-1 轮：
    对每条边 (a, b, c)：
        若 dist[a] + c < dist[b]，则更新 dist[b]

无负权环时它一定收敛到正确答案，并且能自然处理「不可达」——这类点的 dist 始终保持 INF，不会被任何松弛命中。

代码

本解法不单独给出代码文件：它只是用来暴露瓶颈的接力层，正解在渐近复杂度上完全取代了它；真正的可提交实现在正解的 ### 代码 中（main.py）。

复杂度

每轮要扫过全部 $E = 2R + P$ 条边，共 $T - 1$ 轮：

O\bigl(T(2R + P)\bigr)

瓶颈

代入最大数据 $T = 2.5 \times 10^4$ 与 $R = P = 5 \times 10^4$ ：

2.5 \times 10^4 \times (10^5 + 5 \times 10^4) \approx 3.75 \times 10^9

即便单次操作再便宜，这个量级也远超时间限制。SPFA 的平均表现好得多，但最坏复杂度与 Bellman-Ford 同阶，本题作为最短路专题题，数据里显然有针对它的构造。

瓶颈的根源很清楚：负权边让 Dijkstra 无法直接使用，于是被迫退化成「反复扫描全图」。

正解

关键观察

题面那条看起来很奇怪的保证，正是为负权边量身定做的。把它翻译成「道路连通块」的语言：

只走道路时，图被分成若干连通块，块内边权全部非负。
把每个块收缩成一个超级点，航线成为超级点之间的有向边。上面的保证说明这张超级点图没有环，即它是一张 DAG。
因此超级点存在拓扑序。

下面这张图展示了样例的三层结构：原图 → 按道路缩点 → 航线在超级点上构成 DAG。

graph LR
  subgraph L1["原图"]
    n1((1)) ---|5| n2((2))
    n3((3)) ---|5| n4((4))
    n5((5)) ---|10| n6((6))
    n3 -.->|-100| n5
    n4 -.->|-100| n6
    n1 -.->|-10| n3
  end
  subgraph L2["缩点后的 DAG"]
    A((A: 1,2)) -->|-10/-100| B((B: 3,4))
    B -->|-100| C((C: 5,6))
  end

实线是双向道路，虚线是单向航线。缩点后 $A \to B \to C$ 是一条链，三个超级点的入度分别是 $0, 1, 2$ ，拓扑序唯一（ $A, B, C$ ）。可以看出所有负权边都被推到了超级点之间的边上，块内部只剩非负的道路。

思路

Dijkstra 的死穴是「负权边可能让已经出堆的点再次被更新」。拓扑序恰好给出了一个精确的时机：

按拓扑序处理块 $c$ 时，所有跨块航线 $x \to c$ 的起点块 $x$ 都已经处理完毕。所以块 $c$ 中每个点「从块外拿到」的距离值不可能再变小了。

换句话说，跨块负权边不再构成障碍——它们会在轮到目标块之前全部松弛完毕，形成确定的初值。而块内只剩下非负的道路边，可以直接跑 Dijkstra。

于是算法分成三步：

缩点：对每个未访问的城镇做一次只走道路的 BFS，得到一个连通块，记录 comp[v] 与块的成员表。
拓扑排序：在超级点层面加入所有航线边并统计入度，用 Kahn 算法求拓扑序。
逐块 Dijkstra：处理块 $c$ 时，把块内所有 dist 有限的点作为多源起点建堆，跑一次局部 Dijkstra。出堆点 $u$ 时，松弛它的道路边（入堆）和航线边（跨块的只更新 dist，不入本块的堆）。块 $c$ 结束后，把它指向的块入度减 $1$ ，归零者入队。

样例的处理过程如下表，可以逐列对照上面的算法步骤：

步骤	处理的块	压入堆的起点	结果
1	$A = \{1,2\}$	块内 `dist` 全为 `INF`， $S=4$ 不在 $A$ → 堆空	$A$ 内全部保持 `NO PATH`
2	$B = \{3,4\}$	`dist[4] = 0`（起点）	出堆 4：航线 $4 \to 6$ 写入 `dist[6] = -100`（跨块，不入堆）；道路 $4 - 3$ 松弛出 `dist[3] = 5` 入堆；出堆 3：航线 $3 \to 5$ 写入 `dist[5] = -95`（跨块，不入堆）
3	$C = \{5,6\}$	由 $B$ 的航线送来的初值：`(-100, 6)` 与 `(-95, 5)`	块内道路 $5 - 6(10)$ 试松弛一次： $-95 + 10 = -85 > -100$ ，不更新

最终 dist = [∞, ∞, 5, 0, -95, -100]，与样例输出一致。

注意步骤 1： $A$ 虽然是拓扑序的第一个块，但 $S$ 不在其中，块内所有点的 dist 都是 INF，建堆时被 dist[u] < INF 过滤掉，堆空——松弛循环体一次也不会执行，因此不会向 $B$ 写入任何值，也不会污染结果。

再注意步骤 2 与 3 的分工：4→6 这条负权航线在块 $B$ 里被松弛时，没有把 6 压进 $B$ 的堆——6 属于块 $C$ 。它只是把 dist[6] 改成一个更小的值，等块 $C$ 被处理时作为初值参与堆。这正是「块内只有非负边，Dijkstra 安全」的保证所在。

代码

Python 版：

python

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
81
82
83
84
85#!/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-09-30 15:06
# update_at: 2026-09-30 15:06

import sys
from heapq import heappop, heappush
from collections import deque

INF = 1 << 60  # 不可达哨兵，远大于任何真实最短路（≤ T·10^4）


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T, R, P = next(data), next(data), next(data)
    S = next(data)

    # roads：双向非负权边；planes：单向可负权边
    roads: list[list[tuple[int, int]]] = [[] for _ in range(T + 1)]
    planes: list[list[tuple[int, int]]] = [[] for _ in range(T + 1)]
    for _ in range(R):
        a, b, c = next(data), next(data), next(data)
        roads[a].append((b, c))
        roads[b].append((a, c))
    for _ in range(P):
        a, b, c = next(data), next(data), next(data)
        planes[a].append((b, c))

    # 第一步：道路双向，所在连通块内部能自由走动 —— 缩成一个点
    comp = [-1] * (T + 1)
    members: list[list[int]] = []  # 每个块的成员，用于给块内 Dijkstra 建多源堆
    for s in range(1, T + 1):
        if comp[s] != -1:
            continue
        comp[s] = len(members)
        block = [s]
        q = deque([s])
        while q:
            u = q.popleft()
            for v, _ in roads[u]:
                if comp[v] == -1:
                    comp[v] = len(members)
                    block.append(v)
                    q.append(v)
        members.append(block)

    # 第二步：航线必然跨块（块内航线会违反题面保证），缩点后构成 DAG，用入度定拓扑序
    dag: list[list[int]] = [[] for _ in members]
    indeg = [0] * len(members)
    for a in range(1, T + 1):
        for b, _ in planes[a]:
            dag[comp[a]].append(comp[b])
            indeg[comp[b]] += 1

    # 第三步：按拓扑序逐块 Dijkstra。处理块 c 时，所有指向它的跨块航线起点
    # 都已定值，块内每个点的答案也就此确定，负权不会破坏 Dijkstra 的前提。
    dist = [INF] * (T + 1)
    dist[S] = 0
    topo = deque(c for c in range(len(members)) if indeg[c] == 0)
    while topo:
        c = topo.popleft()
        heap = sorted((dist[u], u) for u in members[c] if dist[u] < INF)
        while heap:
            d, u = heappop(heap)
            if d > dist[u]:
                continue
            for v, w in planes[u]:  # 跨块航线：只是给别的块送初值，不入本块的堆
                if d + w < dist[v]:
                    dist[v] = d + w
            for v, w in roads[u]:  # 道路权非负，Dijkstra 安全
                if d + w < dist[v]:
                    dist[v] = d + w
                    heappush(heap, (dist[v], v))
        for y in dag[c]:
            indeg[y] -= 1
            if indeg[y] == 0:
                topo.append(y)

    sys.stdout.write('\n'.join('NO PATH' if dist[i] == INF else str(dist[i]) for i in range(1, T + 1)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190/**
 * 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-05 05:11
 * update_at: 2026-10-05 05:12
 */
// main.cpp：道路连通块缩点 + 拓扑序 + 逐块 Dijkstra（USACO 2011 Jan Gold 道路和航线）。
// 负权航线被限制在块间、由拓扑序消化；块内只有非负道路，Dijkstra 安全。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, int> Node; // 堆元素：first 为距离，second 为城镇编号

const int MAXT = 25005; // 城镇数上限
const int MAXR = 50005; // 道路数上限
const int MAXP = 50005; // 航线数上限

const ll INF = 1000000000000000000LL; // 不可达哨兵，远大于任何真实最短路绝对值

int T, R, P, S; // T<=2.5e4，R,P<=5e4，用 int 可直接当下标与循环上界

// 道路：无向非负权。链式前向星存双向边，故开 2*MAXR。
int head_road[MAXT], to_road[2 * MAXR], nxt_road[2 * MAXR];
int w_road[2 * MAXR]; // 道路边权 0..10^4，用 int 省内存
int road_cnt;

// 航线：有向可负权。
int head_plane[MAXT], to_plane[MAXP], nxt_plane[MAXP];
int w_plane[MAXP]; // 航线边权 -10^4..10^4，用 int 省内存
int plane_cnt;

int comp[MAXT];            // comp[u] = 城镇 u 所属道路连通块编号（从 0 开始）
int comp_cnt;              // 道路连通块总数
vector<int> members[MAXT]; // members[c] = 第 c 个连通块内的城镇列表
vector<int> dag[MAXT];     // dag[c] = 超级点 c 经航线指向的超级点
int indeg[MAXT];           // 超级点入度，用于 Kahn 拓扑排序
ll dist[MAXT];             // dist[u] = 起点 S 到城镇 u 的最短路，INF 表示不可达

// 加一条无向道路（拆成两条有向边）。
void add_road(int u, int v, int w) {
    road_cnt++;
    to_road[road_cnt] = v;
    w_road[road_cnt] = w;
    nxt_road[road_cnt] = head_road[u];
    head_road[u] = road_cnt;
}

// 加一条单向航线。
void add_plane(int u, int v, int w) {
    plane_cnt++;
    to_plane[plane_cnt] = v;
    w_plane[plane_cnt] = w;
    nxt_plane[plane_cnt] = head_plane[u];
    head_plane[u] = plane_cnt;
}

void read_input() {
    cin >> T >> R >> P >> S;
    for (int i = 1; i <= R; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add_road(a, b, c);
        add_road(b, a, c);
    }
    for (int i = 1; i <= P; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add_plane(a, b, c);
    }
}

// 只走道路做 BFS，把每个城镇归入一个道路连通块。
void build_components() {
    int que[MAXT];
    for (int s = 1; s <= T; s++) {
        if (comp[s] != -1) continue;
        int c = comp_cnt;
        comp_cnt++;
        comp[s] = c;
        members[c].push_back(s);
        int head = 0, tail = 0;
        que[tail] = s;
        tail++;
        while (head < tail) {
            int u = que[head];
            head++;
            for (int i = head_road[u]; i != 0; i = nxt_road[i]) {
                int v = to_road[i];
                if (comp[v] == -1) {
                    comp[v] = c;
                    members[c].push_back(v);
                    que[tail] = v;
                    tail++;
                }
            }
        }
    }
}

// 把航线投影到超级点上，得到块间 DAG 与各超级点入度。
void build_dag() {
    for (int a = 1; a <= T; a++) {
        for (int i = head_plane[a]; i != 0; i = nxt_plane[i]) {
            int b = to_plane[i];
            if (comp[a] == comp[b]) continue; // 题面保证不存在块内航线，这里防御性跳过
            dag[comp[a]].push_back(comp[b]);
            indeg[comp[b]]++;
        }
    }
}

// 按拓扑序逐块 Dijkstra：块内负权已由块外航线送入初值，块内只剩非负道路。
void solve() {
    dist[S] = 0;
    priority_queue<Node, vector<Node>, greater<Node> > heap;
    queue<int> topo;
    for (int c = 0; c < comp_cnt; c++) {
        if (indeg[c] == 0) topo.push(c);
    }
    while (!topo.empty()) {
        int c = topo.front();
        topo.pop();

        // 块内所有已定值的城镇作为多源起点，只遍历本块成员，避免扫描全部城镇。
        for (size_t k = 0; k < members[c].size(); k++) {
            int u = members[c][k];
            if (dist[u] < INF) heap.push(Node(dist[u], u));
        }

        while (!heap.empty()) {
            Node cur = heap.top();
            heap.pop();
            ll d = cur.first;
            int u = cur.second;
            if (d > dist[u]) continue;

            // 跨块航线：只更新目标块的距离，绝不入本块的堆（目标块的点尚未定值）。
            for (int i = head_plane[u]; i != 0; i = nxt_plane[i]) {
                int v = to_plane[i];
                ll nd = d + w_plane[i];
                if (nd < dist[v]) dist[v] = nd;
            }
            // 道路权非负，Dijkstra 安全。
            for (int i = head_road[u]; i != 0; i = nxt_road[i]) {
                int v = to_road[i];
                ll nd = d + w_road[i];
                if (nd < dist[v]) {
                    dist[v] = nd;
                    heap.push(Node(nd, v));
                }
            }
        }

        // 当前块处理完毕，给它在 DAG 中的后继块减少入度。
        for (size_t k = 0; k < dag[c].size(); k++) {
            int y = dag[c][k];
            indeg[y]--;
            if (indeg[y] == 0) topo.push(y);
        }
    }
}

void write_output() {
    for (int i = 1; i <= T; i++) {
        if (dist[i] == INF) cout << "NO PATH" << '\n';
        else cout << dist[i] << '\n';
    }
}

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

    read_input();

    // 只初始化实际用到的 1..T，其余下标永远不会被访问。
    for (int i = 1; i <= T; i++) {
        comp[i] = -1;
        dist[i] = INF;
    }

    build_components();
    build_dag();
    solve();
    write_output();

    return 0;
}

复杂度

阶段	代价
缩点 BFS	每条道路访问一次， $O(T + R)$
建 DAG、统计入度	每条航线一次， $O(T + P)$
拓扑排序	$O(T + P)$
逐块 Dijkstra	每条边最多参与一次堆操作， $O((R + P)\log T)$

总时间复杂度：

O\bigl((T + R + P)\log T\bigr)

比 Bellman-Ford 的 $O\bigl(T(R + P)\bigr)$ 少乘了一个 $T$ 。空间复杂度 $O(T + R + P)$ 。

总结

这道题的关键在于看穿题面保证的图论含义：那条「有航线 $A \to B$ 就回不到 $A$ 」的约束，等价于「道路连通块缩点后是 DAG」。一旦得到 DAG，就拿到了拓扑序；而拓扑序恰好提供了 Dijkstra 最需要的东西——一个「块外距离值已定」的时机。于是负权边被限制在块间、由拓扑序消化，块内退回非负图、由 Dijkstra 处理。

实现上有两个容易踩的坑：一是建堆时必须只遍历当前块的成员，若每个块都扫描全部 $T$ 个点会退化成 $O(T \times \text{块数})$ ，在块数接近 $T$ 的数据（如 24999 个孤立块）上直接超时；二是跨块航线松弛后不能入本块的堆，否则会把别的块的点提前当作已定值处理，破坏正确性。

本解法在全部 16 个官方测试点上通过，最慢 0.114 秒、峰值内存 63.6MB，Python 实现也在限制内（1000ms / 128MB）。