Freda的传呼机

形式化题目

给定一张 $N$ 个点、 $M$ 条边的连通无向带权图，其中每条边至多属于一个环（即题面 A、B、C 三类结构合并后的仙人掌图）。给出 $Q$ 次询问，每次给定两个点 $x, y$ ，求它们之间路径边权和的最小值。

正解

思路

朴素做法。 每次询问对 $x$ 跑一遍 Dijkstra 求到 $y$ 的最短路：单次 $O(M\log N)$ ， $Q$ 次就是 $O(QM\log N)$ ，在 $Q = 10000$ 、 $M \leqslant 12000$ 的规模下必然超时。瓶颈在于 $Q$ 次询问重复扫描了同一张图，所以要把图的结构一次性预处理出来，让每次询问只花 $O(\log N)$ 。

图长什么样。 三类结构 A（ $M=N-1$ ，树）、B（ $M=N$ ，一个环）、C（每个环互不共享边）合起来只有一句话： $M-(N-1)$ 条"多余"的边，每条边至多属于一个环——环与环最多"点接触"，这就是仙人掌图。下图是一个典型例子：一个三角形与一个四边形共享顶点 $3$ ，另外还挂着桥边。

graph LR
    subgraph cactus["原图（仙人掌）"]
        1 ---|3| 2
        2 ---|4| 3
        3 ---|5| 1
        3 ---|7| 4
        4 ---|2| 5
        5 ---|2| 6
        6 ---|3| 4
        3 ---|1| 8
    end

先找环。 任取一棵生成树（ $N-1$ 条边），剩下 $M-(N-1)$ 条非树边。每加一条非树边就形成唯一一个环，而仙人掌里这条非树边只属于这一个环，于是每条非树边恰好对应一个环：浅的一端是环顶 $top$ ，深的一端是环底 $bottom$ ，环就是「生成树上 $top \rightsquigarrow bottom$ 的路径 + 这条非树边」。同一条非树边会被两个方向各扫到一次，用一个标记数组去重即可。

把环缩成方点。 每个环新建一个方点（编号 $N+r$ ），原图的顶点叫圆点：

原图对象	圆方树中的写法
环顶 $top$	方点的父节点（方点父边权 $0$ ）
环上其他点 $v$	父节点是这个方点，父边权 $\min(pos_v,\ L - pos_v)$
桥边 $(u,v)$	保持为树边，权取原边权

其中 $pos_v$ 是"环顶沿生成树弧到 $v$ "的距离， $L$ 是环长（生成树弧长 + 非树边权）。每种取法都把"环内二选一取短"提前算好，于是环顶到环上任意点的最短路就是方树上的父边权。

graph TD
    subgraph tree["圆方树（方点 S1、S2 代表两个环）"]
        1 --> S1(("S1"))
        3 --> S1
        2 --> S1
        S1 --> n3["3"]
        n3 --> S2(("S2"))
        4 --> S2
        S2 --> n4["4"]
        n4 --> n5["5"]
        n5 --> n6["6"]
        n3 --> n8["8"]
    end

把每个环压成方点后得到一棵树，以 $1$ 为根做一次遍历，令 $\text{sd}[v]$ 为根到 $v$ 的方树距离。关键性质： $\text{sd}[v]$ 恰好等于原图中 $1$ 到 $v$ 的最短路长度——因为进入任何环的入口都是该环的环顶（环顶一定是割点），而环顶到环上各点的最短路正是前面设置的父边权。

回答询问。 设 $a = \operatorname{LCA}(x, y)$ （圆方树上）：

LCA 类型	含义	答案
圆点（ $a \leqslant N$ ）	两条路径在环之前就分开，环内不产生合流	$\text{sd}[x] + \text{sd}[y] - 2\,\text{sd}[a]$
方点（ $a > N$ ）	两条路径从环上不同顶点 $ax, ay$ 进入同一个环	$\bigl(\text{sd}[x]-\text{sd}[ax]\bigr) + \bigl(\text{sd}[y]-\text{sd}[ay]\bigr) + \min(d, L-d)$

方点情形里， $ax$ 与 $ay$ 分别是 $x$ 、 $y$ 向上跳到方点的那两个儿子， $d = \lvert pos_{ax} - pos_{ay}\rvert$ ， $L$ 是这个环的环长；环内两点之间只有两条弧可选，取短的那条。由于边权都是正数，绕整圈不可能更优。

样例验证（样例是一棵树，只走第一行公式）：

询问	路径	答案
`3 5`	$3 \to 1 \to 2 \to 5$ ， $1+1+1$	3
`2 1`	$2 \to 1$	1

与样例输出一致。为了确认公式在环上成立，另外用随机仙人掌生成器与本机 Dijkstra 对拍了 5000 组小数据（纯树、单环、共享顶点的三角形链、大环挂树四种形态），结果全部一致。

代码

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
191
192
193/**
 * 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-10 13:30
 * update_at: 2026-10-10 13:30
 */

// Freda 的传呼机：仙人掌最短路 —— 建圆方树（每个环缩成挂在环顶下的方点），
// 环上非顶点的父边权取「环顶沿环内最短路到它」的距离，于是方树距离 = 仙人掌最短路；
// 询问的 LCA 是方点时再在环内取一条弧。
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXN = 10005;   // 圆点个数
const int MAXEDGE = 12005; // 边数
const int MAXTOT = 30005; // 圆方树总点数
const int MAXLOG = 20;

int n, m, q, tot;
int head[MAXN + 2];
int toArr[2 * MAXEDGE], wtArr[2 * MAXEDGE], eidArr[2 * MAXEDGE];
int par[MAXN + 1], pare[MAXN + 1], dep[MAXN + 1];
ll dtree[MAXN + 1];
vector<vector<int> > rings; // 每个环的顶点表（环顶在前）
vector<vector<ll> > arcs;   // 环顶沿生成树到各点的距离
vector<ll> ringW;           // 每个环的真环长

int sqPar[MAXTOT + 1], sqDep[MAXTOT + 1];
ll sqW[MAXTOT + 1], sqPos[MAXTOT + 1], sd[MAXTOT + 1];
vector<int> sqChildren[MAXTOT + 1];
int up[MAXLOG][MAXTOT + 1];

void readGraph(const vector<int> &ex, const vector<int> &ey, const vector<int> &ew) {
    // CSR 邻接表：v 的出边在 [head[v], head[v+1])，按输入顺序
    vector<int> deg(n + 2, 0);
    for (int i = 0; i < m; ++i) {
        deg[ex[i]] += 1;
        deg[ey[i]] += 1;
    }
    head[0] = 0;
    head[1] = 0;
    for (int v = 1; v <= n; ++v) head[v + 1] = head[v] + deg[v];
    vector<int> fill(head, head + n + 2);
    for (int i = 0; i < m; ++i) {
        int j = fill[ex[i]];
        toArr[j] = ey[i]; wtArr[j] = ew[i]; eidArr[j] = i; fill[ex[i]] = j + 1;
        j = fill[ey[i]];
        toArr[j] = ex[i]; wtArr[j] = ew[i]; eidArr[j] = i; fill[ey[i]] = j + 1;
    }
}

void findRings() { // 迭代 DFS 建生成树，再让每条非树边圈出它所在的环
    vector<int> seen(n + 1, 0), used(m, 0);
    vector<int> ptr(head, head + n + 2), stk;
    for (int i = 1; i <= n; ++i) pare[i] = -1;
    seen[1] = 1;
    stk.push_back(1);
    while (!stk.empty()) {
        int v = stk.back();
        int j = ptr[v];
        if (j >= head[v + 1]) { // v 的出边扫完了
            stk.pop_back();
            continue;
        }
        ptr[v] = j + 1;
        if (eidArr[j] == pare[v]) continue; // 这条正是通向父节点的树边
        int u = toArr[j];
        if (seen[u]) {
            if (!used[eidArr[j]]) { // 两端都访问过，它就是非树边
                used[eidArr[j]] = 1;
                int top, bottom;
                if (dep[u] < dep[v]) { top = u; bottom = v; }
                else { top = v; bottom = u; }
                vector<int> nodes;
                vector<ll> arc;
                nodes.push_back(bottom);
                arc.push_back(dtree[bottom] - dtree[top]);
                int x = par[bottom];
                while (x != top) {
                    nodes.push_back(x);
                    arc.push_back(dtree[x] - dtree[top]);
                    x = par[x];
                }
                nodes.push_back(top);
                arc.push_back(0);
                reverse(nodes.begin(), nodes.end()); // 排成从环顶到环底
                reverse(arc.begin(), arc.end());
                rings.push_back(nodes);
                arcs.push_back(arc);
                ringW.push_back(arc.back() + wtArr[j]); // 生成树弧长 + 非树边 = 真环长
            }
            continue;
        }
        seen[u] = 1;
        par[u] = v; pare[u] = eidArr[j]; dep[u] = dep[v] + 1;
        dtree[u] = dtree[v] + wtArr[j];
        stk.push_back(u);
    }
}

void buildSquareTree() {
    tot = n + rings.size();
    for (int v = 2; v <= n; ++v) { // 不在环里的点：父边就是生成树的边
        sqPar[v] = par[v];
        sqW[v] = dtree[v] - dtree[par[v]];
    }
    for (int r = 1; r <= (int)rings.size(); ++r) {
        int S = n + r;
        ll L = ringW[r - 1];
        sqPar[S] = rings[r - 1][0]; // 方点挂在环顶下，边权 0
        for (int t = 1; t < (int)rings[r - 1].size(); ++t) {
            int v = rings[r - 1][t];
            ll pos = arcs[r - 1][t];
            sqPar[v] = S;
            sqW[v] = min(pos, L - pos); // 环顶到 t 的两条弧取短
            sqPos[v] = pos;             // t 在父环上的弧长坐标
        }
    }
    for (int v = 2; v <= tot; ++v) sqChildren[sqPar[v]].push_back(v);
    vector<int> order; // 层序遍历：同时算方树深度与根到点最短路
    order.push_back(1);
    for (int i = 0; i < (int)order.size(); ++i) {
        int v = order[i];
        for (int j = 0; j < (int)sqChildren[v].size(); ++j) {
            int c = sqChildren[v][j];
            sqDep[c] = sqDep[v] + 1;
            sd[c] = sd[v] + sqW[c];
            order.push_back(c);
        }
    }
}

int upK(int x, int k, int rows) { // 把 x 向上跳恰好 k 步
    int i = 0;
    while (k) {
        if (k & 1) x = up[i][x];
        k >>= 1;
        ++i;
    }
    return x;
}

int lca(int x, int y, int rows) {
    if (sqDep[x] < sqDep[y]) { int t = x; x = y; y = t; }
    x = upK(x, sqDep[x] - sqDep[y], rows);
    if (x == y) return x;
    for (int i = rows - 1; i >= 0; --i) {
        if (up[i][x] != up[i][y]) { x = up[i][x]; y = up[i][y]; }
    }
    return up[0][x];
}

int main() {
    if (scanf("%d %d %d", &n, &m, &q) != 3) return 0; // 空输入安全返回
    vector<int> ex(m), ey(m), ew(m);
    for (int i = 0; i < m; ++i) scanf("%d %d %d", &ex[i], &ey[i], &ew[i]);
    readGraph(ex, ey, ew);
    findRings();
    buildSquareTree();

    int rows = 1;
    while ((1 << rows) <= tot) ++rows; // rows = tot.bit_length()
    if (rows < 1) rows = 1;
    if (rows > MAXLOG) rows = MAXLOG;
    for (int v = 0; v <= tot; ++v) up[0][v] = sqPar[v];
    for (int k = 1; k < rows; ++k) {
        for (int v = 0; v <= tot; ++v) up[k][v] = up[k - 1][up[k - 1][v]];
    }

    for (int i = 0; i < q; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        int a = lca(x, y, rows);
        if (a <= n) { // LCA 是圆点：两端最短路互不干扰
            printf("%lld\n", sd[x] + sd[y] - 2 * sd[a]);
        } else { // LCA 是方点：看清两端各自从环的哪个点进来，再在环内选一条弧
            int ax = upK(x, sqDep[x] - sqDep[a] - 1, rows);
            int ay = upK(y, sqDep[y] - sqDep[a] - 1, rows);
            ll d = sqPos[ax] - sqPos[ay];
            if (d < 0) d = -d;
            ll L = ringW[a - n - 1];
            ll other = L - d;
            printf("%lld\n", sd[x] + sd[y] - sd[ax] - sd[ay] + (d < other ? d : other));
        }
    }
    if (q == 0) printf("\n"); // 复刻 py 的空 out 仍输出一个换行
    return 0;
}

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
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#!/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-02 01:20
# update_at: 2026-10-02 01:20

import sys
from itertools import accumulate

# 方树编号约定：1..n 是原来的房屋（圆点），n+1..n+rings 是每个环缩成的方点。


def read_graph(xs: list[int], ys: list[int], ws: list[int], n: int, m: int):
    """把 M 条边做成 CSR 邻接表：head[v] 是 v 的出边在 to/wt/eid 里的起始下标。"""
    deg = [0] * (n + 2)
    for x, y in zip(xs, ys):
        deg[x] += 1
        deg[y] += 1
    head = [0, 0] + list(accumulate(deg[1 : n + 1]))  # head[v+1] = head[v] + deg[v]
    fill = head[:]
    to, wt, eid = [0] * (2 * m), [0] * (2 * m), [0] * (2 * m)
    for i, (x, y, w) in enumerate(zip(xs, ys, ws)):
        j = fill[x]
        to[j], wt[j], eid[j], fill[x] = y, w, i, j + 1
        j = fill[y]
        to[j], wt[j], eid[j], fill[y] = x, w, i, j + 1
    return head, to, wt, eid


def find_rings(n: int, head, to, wt, eid):
    """迭代 DFS 建生成树，再让每条非树边圈出它所在的环。

    非树边 (top, bottom) 的浅端点是环顶、深端点是环底，环 = 生成树 top..bottom 这一段
    加上这条非树边；每个环返回「环顶点表（环顶在前）」和「环顶沿生成树到各点的距离」。
    """
    par, pare, dep, dtree = [0] * (n + 1), [-1] * (n + 1), [0] * (n + 1), [0] * (n + 1)
    rings: list[list[int]] = []
    arcs: list[list[int]] = []
    ring_w: list[int] = []
    seen, used = bytearray(n + 1), bytearray(len(eid))  # used：已认领为「非树边」的边
    seen[1] = 1
    ptr, stack = head[:], [1]
    while stack:
        v = stack[-1]
        j = ptr[v]
        if j >= head[v + 1]:  # v 的出边扫完了
            stack.pop()
            continue
        ptr[v] = j + 1
        if eid[j] == pare[v]:  # 这条正是通向父节点的树边
            continue
        u = to[j]
        if seen[u]:
            if not used[eid[j]]:  # 两端都访问过，它就是非树边
                used[eid[j]] = 1
                top, bottom = (u, v) if dep[u] < dep[v] else (v, u)
                nodes, arc = [bottom], [dtree[bottom] - dtree[top]]
                x = par[bottom]
                while x != top:
                    nodes.append(x)
                    arc.append(dtree[x] - dtree[top])
                    x = par[x]
                nodes.append(top)
                arc.append(0)
                nodes.reverse()  # 排成从环顶到环底
                arc.reverse()
                rings.append(nodes)
                arcs.append(arc)
                ring_w.append(arc[-1] + wt[j])  # 生成树弧长 + 非树边 = 真环长
            continue
        seen[u] = 1
        par[u], pare[u], dep[u] = v, eid[j], dep[v] + 1
        dtree[u] = dtree[v] + wt[j]
        stack.append(u)
    return par, dtree, rings, arcs, ring_w


def build_square_tree(n: int, par, dtree, rings, arcs, ring_w):
    """每个环缩成一个挂在环顶下的方点，得到圆方树。

    非环点的父节点就是生成树父节点；环上非顶点的父节点是方点，父边权取「环顶沿环内
    最短路到它」的距离，于是根到各点的方树距离恰好等于仙人掌上的最短路。
    """
    tot = n + len(rings)
    sq_par, sq_w, sq_pos = [0] * (tot + 1), [0] * (tot + 1), [0] * (tot + 1)
    for v in range(2, n + 1):
        sq_par[v] = par[v]
        sq_w[v] = dtree[v] - dtree[par[v]]  # 不在环里的点：父边就是生成树的边
    for r, (nodes, arc) in enumerate(zip(rings, arcs), 1):
        S = n + r
        L = ring_w[r - 1]
        sq_par[S] = nodes[0]  # 方点挂在环顶下，边权 0
        for t, pos in zip(nodes[1:], arc[1:]):
            sq_par[t] = S
            sq_w[t] = min(pos, L - pos)  # 环顶到 t 的两条弧取短
            sq_pos[t] = pos  # t 在「父环」上的弧长坐标，供方点 LCA 的询问用
    children = [[] for _ in range(tot + 1)]
    for v in range(2, tot + 1):
        children[sq_par[v]].append(v)
    sq_dep, sd = [0] * (tot + 1), [0] * (tot + 1)
    order, i = [1], 0
    while i < len(order):  # 层序遍历，同时算方树深度与根到点最短路
        v = order[i]
        i += 1
        for c in children[v]:
            sq_dep[c] = sq_dep[v] + 1
            sd[c] = sd[v] + sq_w[c]
            order.append(c)
    return sq_par, sq_dep, sd, sq_pos, tot


def up_k(up, x: int, k: int) -> int:
    """在方树上把 x 向上跳恰好 k 步（二进制拆分）。"""
    i = 0
    while k:
        if k & 1:
            x = up[i][x]
        k >>= 1
        i += 1
    return x


def lca(up, sq_dep: list[int], log: int, x: int, y: int) -> int:
    """圆方树上 x 与 y 的最近公共祖先。"""
    if sq_dep[x] < sq_dep[y]:
        x, y = y, x
    x = up_k(up, x, sq_dep[x] - sq_dep[y])
    if x == y:
        return x
    for i in range(log - 1, -1, -1):
        if up[i][x] != up[i][y]:
            x, y = up[i][x], up[i][y]
    return up[0][x]


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

    edges = [(next(data), next(data), next(data)) for _ in range(m)]
    xs = [x for x, _, _ in edges]
    ys = [y for _, y, _ in edges]
    ws = [w for _, _, w in edges]

    head, to, wt, eid = read_graph(xs, ys, ws, n, m)
    par, dtree, rings, arcs, ring_w = find_rings(n, head, to, wt, eid)
    sq_par, sq_dep, sd, sq_pos, tot = build_square_tree(n, par, dtree, rings, arcs, ring_w)

    log = max(1, tot.bit_length())
    up = [sq_par]  # up[k][v] = v 的 2^k 级祖先，up[0] 就是父指针
    for _ in range(1, log):
        prev = up[-1]
        up.append([prev[prev[v]] for v in range(tot + 1)])

    out: list[int] = []
    for _ in range(q):
        x, y = next(data), next(data)
        a = lca(up, sq_dep, log, x, y)
        if a <= n:  # LCA 是圆点：两端最短路互不干扰，直接由方树距离相减
            out.append(sd[x] + sd[y] - 2 * sd[a])
        else:  # LCA 是方点：要看清两端各自从环的哪个点进来，再在环内选一条弧
            ax = up_k(up, x, sq_dep[x] - sq_dep[a] - 1)
            ay = up_k(up, y, sq_dep[y] - sq_dep[a] - 1)
            d = abs(sq_pos[ax] - sq_pos[ay])
            out.append(sd[x] + sd[y] - sd[ax] - sd[ay] + min(d, ring_w[a - n - 1] - d))
    sys.stdout.write("\n".join(map(str, out)) + "\n")


if __name__ == "__main__":
    solve()

复杂度

时间： $O\bigl((N+M)\log(N+M) + Q\log N\bigr)$ 。建生成树、圈环、建圆方树各是线性；倍增表占 $O((N+M)\log(N+M))$ ；每次询问一次 LCA 加上至多两次 $O(\log N)$ 跳步。
空间： $O\bigl((N+M)\log(N+M)\bigr)$ ，主要来自倍增祖先表 up。

总结

本题的核心是把"图上多次询问最短路"化成"树上距离 + 至多一处环内取短"：

题面 A/B/C 三类结构等价于仙人掌，于是"每条非树边恰好圈出一个环"，用一次迭代 DFS 就能把全部环找出来。
把每个环缩成方点、环上各点按"环顶到它的最短路"设置父边权，得到圆方树；根到点的方树距离就是原图最短路。
询问时按 LCA 是圆点还是方点分两类：圆点直接相减，方点在环内取两条弧中较短的一条。

用 Python 实现时注意两点：DFS 写成显式栈避免深递归；输入一次读完再用切片取三列，比逐 token next() 更快。

目录

形式化题目

正解

思路

代码

复杂度

总结