「一本通 3.2 练习 1」农场派对

形式化题目

给定一个包含 $N$ 个顶点和 $M$ 条有向带权边的有向图 $G = (V, E)$ ，边权均为正整数，以及一个指定的目标顶点 $X$ 。

定义两点 $u, v$ 之间的最短路长度为 $\operatorname{dist}(u, v)$ 。对于每个顶点 $i \in \{1, 2, \dots, N\}$ ，其“往返最短路径长度”为：

\operatorname{round\_trip}(i) = \operatorname{dist}(i, X) + \operatorname{dist}(X, i)

求所有顶点中往返最短路径长度的最大值，即：

\max_{1 \leqslant i \leqslant N} \operatorname{round\_trip}(i)

正解

思路

计算每个顶点的往返最短路可分为两个独立的部分：

回程部分：从目标顶点 $X$ 出发到达每个顶点 $i$ 的最短路 $\operatorname{dist}(X, i)$ ；
去程部分：从每个顶点 $i$ 出发到达目标顶点 $X$ 的最短路 $\operatorname{dist}(i, X)$ 。

对于回程部分，这本质上是以 $X$ 为起点的单源最短路径（SSSP）问题。在原图 $G$ 上，以 $X$ 作为源点执行一次堆优化的 Dijkstra 算法，即可在 $O(M \log N)$ 时间内求出 $X$ 到所有顶点的最短距离 $\operatorname{dist}(X, i)$ 。

对于去程部分，如果对每个顶点 $i$ 都单独执行一次单源最短路算法，总共需要运行 $N$ 次 Dijkstra，时间复杂度高达 $O(N \cdot M \log N)$ ，在 $N = 1000, M = 100000$ 的数据规模下会严重超出时限。

这里可以借助**反向图（Reverse Graph）**的性质进行优化：

构造原图 $G = (V, E)$ 的反向图 $G^R = (V, E^R)$ ，其中反向边集合定义为 $E^R = \{(v, u, w) \mid (u, v, w) \in E\}$ 。
原图中任意一条由 $i$ 到 $X$ 且权重和为 $W$ 的有向路径：
$i = v_0 \xrightarrow{w_1} v_1 \xrightarrow{w_2} v_2 \cdots \xrightarrow{w_k} v_k = X$
在反向图 $G^R$ 中完全对应一条由 $X$ 到 $i$ 且权重和相同的路径：
$X = v_k \xrightarrow{w_k} v_{k-1} \cdots \xrightarrow{w_2} v_1 \xrightarrow{w_1} v_0 = i$
因此，原图中 $i \to X$ 的最短路长度，严格等于反向图中 $X \to i$ 的最短路长度：
$\operatorname{dist}_G(i, X) = \operatorname{dist}_{G^R}(X, i)$

于是，求所有顶点到 $X$ 的最短路，转化为在反向图 $G^R$ 上以 $X$ 为源点求解单源最短路。只需在 $G^R$ 上再运行一次堆优化 Dijkstra 即可得到所有的 $\operatorname{dist}(i, X)$ 。

算法全流程：

读取输入时同时建立原图的邻接表 adj 与反向图的邻接表 rev_adj；
在原图上以 $X$ 为起点跑一次 Dijkstra，记距离数组为 dist_from_x；
在反向图上以 $X$ 为起点跑一次 Dijkstra，记距离数组为 dist_to_x；
遍历 $i \in [1, N]$ ，取 dist_to_x[i] + dist_from_x[i] 的最大值输出。

flowchart LR
    subgraph G [原图 G: 求 X -> i]
        X1((X)) -->|Dijkstra| I1((各个 i))
    end
    subgraph GR [反向图 GR: 求 i -> X 等价于 X -> i]
        X2((X)) -->|Dijkstra| I2((各个 i))
    end
    G --> Sum["求和 dist(i, X) + dist(X, i)"]
    GR --> Sum
    Sum --> Ans["取全局最大值 max"]

代码

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#!/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 14:40
# update_at: 2026-09-30 14:40

import heapq
import sys

INF = 10**18


def dijkstra(n: int, start: int, adj: list[list[tuple[int, int]]]) -> list[int]:
    """计算从 start 出发到图中所有点的单源最短路距离。"""
    dist = [INF] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    return dist


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m, x = next(data), next(data), next(data)

    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    rev_adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]

    for _ in range(m):
        u, v, w = next(data), next(data), next(data)
        adj[u].append((v, w))
        rev_adj[v].append((u, w))

    dist_from_x = dijkstra(n, x, adj)
    dist_to_x = dijkstra(n, x, rev_adj)

    ans = max(dist_to_x[i] + dist_from_x[i] for i in range(1, n + 1))
    print(ans)


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/**
 * 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 04:33
 * update_at: 2026-10-05 04:33
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1005;    // 农场数上限（N <= 1000）
const int MAXM = 100005;  // 每个图的边数上限（M <= 100000）
const ll INF = 1e18;

int n, m, x; // n 头牛、m 条有向道路、派对农场编号 x

// 正向图：链式前向星，用来求 x 到各点的最短路（回程）
int head[MAXN], nxt[MAXM], to[MAXM];
ll w[MAXM];
int edge_cnt;

// 反向图：把每条边 u->v 倒过来存成 v->u，用来求各点到 x 的最短路（去程）
// 因为原图中 i 到 x 的最短路，等于反向图中 x 到 i 的最短路。
int rev_head[MAXN], rev_nxt[MAXM], rev_to[MAXM];
ll rev_w[MAXM];
int rev_edge_cnt;

ll dist_from_x[MAXN]; // dist_from_x[i]：原图中 x -> i 的最短路长度
ll dist_to_x[MAXN];   // dist_to_x[i]：反向图中 x -> i 的最短路长度，即原图 i -> x

// 向正向图加一条 u -> v、长度 c 的边。
void add_edge(int u, int v, ll c) {
    edge_cnt++;
    to[edge_cnt] = v;
    w[edge_cnt] = c;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 向反向图加一条 u -> v、长度 c 的边（存的是原图 v -> u 的反向边）。
void add_rev_edge(int u, int v, ll c) {
    rev_edge_cnt++;
    rev_to[rev_edge_cnt] = v;
    rev_w[rev_edge_cnt] = c;
    rev_nxt[rev_edge_cnt] = rev_head[u];
    rev_head[u] = rev_edge_cnt;
}

// 堆优化 Dijkstra：在给定的图上求源点 start 到所有点的最短路，结果写入 dist。
// 传入一组链式前向星数组，让正向图与反向图共用同一份松弛逻辑。
void dijkstra(int start, int *g_head, int *g_nxt, int *g_to, ll *g_w, ll *dist) {
    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[start] = 0;

    // 小根堆，元素为 (当前最短路长度, 顶点编号)
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
    pq.push(make_pair(0, start));

    while (!pq.empty()) {
        pair<ll, int> cur = pq.top();
        pq.pop();
        ll d = cur.first;
        int u = cur.second;
        if (d > dist[u]) continue; // 堆里过期的旧记录，直接跳过

        for (int i = g_head[u]; i; i = g_nxt[i]) {
            int v = g_to[i];
            if (dist[u] + g_w[i] < dist[v]) {
                dist[v] = dist[u] + g_w[i];
                pq.push(make_pair(dist[v], v));
            }
        }
    }
}

void read_input() {
    cin >> n >> m >> x;
    for (int i = 1; i <= m; i++) {
        int a, b;
        ll t;
        cin >> a >> b >> t;
        add_edge(a, b, t);     // 原图 a -> b
        add_rev_edge(b, a, t); // 反向图 b -> a，等价于把原边倒过来
    }
}

void solve() {
    // 回程：在原图上以 x 为源点做一次 Dijkstra
    dijkstra(x, head, nxt, to, w, dist_from_x);
    // 去程：在反向图上以 x 为源点做一次 Dijkstra
    dijkstra(x, rev_head, rev_nxt, rev_to, rev_w, dist_to_x);

    // 每头牛的花费是去程加回程，答案取其中最大的一条
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ll round_trip = dist_to_x[i] + dist_from_x[i];
        if (round_trip > ans) ans = round_trip;
    }
    cout << ans << endl;
}

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

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度：建图遍历 $M$ 条边需 $O(M)$ 时间；两次堆优化 Dijkstra 的时间复杂度均为 $O((N + M) \log N)$ ，最后遍历 $N$ 个顶点求最大值耗时 $O(N)$ 。整体时间复杂度为 $O((N + M) \log N)$ ，对于 $N \leqslant 1000, M \leqslant 100000$ 可以在数十毫秒内快速完成。
空间复杂度：存储正向邻接表和反向邻接表各需要 $O(N + M)$ 空间，Dijkstra 堆与距离数组占用 $O(N + M)$ 空间。整体空间复杂度为 $O(N + M)$ ，远低于 128MB 的内存限制。

总结

多源单汇的最短路问题是图论中的经典模型。由于在有向图中“所有点到一个固定终点”等价于“在边全反向的图中从该点出发到所有点”，利用反向图可以将原本需要 $N$ 次的单源最短路规约为单次以目标点为起点的单源最短路，从而将时间复杂度从 $O(N \cdot M \log N)$ 大幅降低到 $O(M \log N)$ 。

「一本通 3.2 练习 1」农场派对

目录

形式化题目

正解

思路

代码

复杂度

总结