GESP 题解库 / 8 级题解 / [GESP202512 八级] 猫和老鼠 · 第 4 / 24 题
GESP202512 八级 · P14923 · 困难

猫和老鼠:谁先到,谁安全

先用 Dijkstra 算出猫到每个点的时间 W(x),再从老鼠洞出发,用"大根堆 + 瓶颈递推"倒推每个点最晚能安全出发的时刻 A(x)。

🐱
n, m ≤ 10⁵
结点数与边数
🧀
cᵢ ≤ 10⁹
奶酪价值
⚡
O((n + m) log n)
两遍类 Dijkstra
🎯
最大最小(瓶颈型)递推
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

猫和老鼠所在的庄园是一张由 n 个点、m 条带权无向边组成的连通图。结点 i 上放有价值 cᵢ 的奶酪;第 i 条边连接 uᵢ 与 vᵢ,边权 wᵢ 表示猫或老鼠通过这条边需要的时间。

猫窝在结点 a,老鼠洞在结点 b。对于老鼠而言,结点 u 是安全的当且仅当:老鼠能规划一条从 u 出发逃往老鼠洞的路径,使得对于路径上的任意结点 x(包含起点 u 与终点 b)都有:猫从猫窝出发到 x 的最短时间 严格大于老鼠从 u 沿这条路径走到 x 所需的时间。

老鼠只敢拿安全结点上的奶酪,求它能拿到的奶酪价值之和。

样例输入输出
样例 15 5
1 2
1 2 4 8 16
1 2 4
2 3 3
3 4 1
2 5 2
3 1 8
22
样例 26 10
3 4
1 1 1 1 1 1
1 2 6
2 3 3
3 1 4
3 4 5
4 5 8
5 6 2
6 4 1
3 2 4
5 4 4
3 3 6
3
💡
人话翻译:老鼠站在 u,挑一条通往 b 的路,路上每一个落脚点都得满足"我到得比猫早"。
注意是严格早,而且是沿这条路径的实际时刻与猫的最短时间比较——猫可以抄近路,老鼠不能抄(老鼠只能走这条路径本身)。
关键转化:时间都是整数,所以"猫的时间 > 老鼠的时间"等价于"老鼠的时刻 ≤ 猫的时间 − 1",把严格不等式变成 ≤,后面就能用整数递推了。

🔍 关键词提取

安全结点判定瓶颈型最短路最大程度松弛大根堆 Dijkstra 变体严格不等式转 ≤连通带权无向图

已知条件

项目说明
输入第 1 行 n、m;第 2 行 a、b;第 3 行 n 个 cᵢ;随后 m 行 uᵢ vᵢ wᵢ
输出一个整数:所有安全结点的奶酪价值之和
数据范围1 ≤ n, m ≤ 10⁵
边权1 ≤ wᵢ ≤ 10⁹
奶酪价值1 ≤ cᵢ ≤ 10⁹(原题缺范围,按此计算)
图的性质连通无向图,可能有平行边、自环
特殊点a ≠ b

需要解决的问题

02
思维导图
整理解题思路的全貌
🛡️ 安全结点 = 存在一条"处处赶在猫前面"的路
① 先把猫的路算清
以猫窝 a 为源跑 Dijkstra
得到 W(x):猫到 x 的最短时间
W(a) = 0,W 单调"向外变大"
W(x) 是老鼠的时间上限来源
② 定义"老鼠的额度" A(x)
A(x) = 老鼠最晚能安全站在 x 的时刻
A(b) = W(b) − 1(洞里的最后一刻)
A(x) = min(W(x) − 1, max(A(y) − w))
u 安全 ⟺ A(u) ≥ 0
③ 为什么用大根堆
瓶颈型:最大化最小值
每次弹出 A 最大的点即定稿
从 b 往外扩张(反向)
扩展时 cand = min(W(v)−1, A(u)−w)
⚠️ 易错点
把比较写成"沿最短路径"而不是"沿这条路径"
忘记严格不等式要减 1
用小根堆(语义反了)
A 与答案用 int 溢出
a 自己永远不安全(A(a) ≤ −1)
03
样例手算推导
样例 1 逐步手推 W、A 与三个安全点,外加一个"看起来安全其实不安全"的反例

🧮 第 ① 步:以猫窝 a = 1 为源,算 W(x)

样例 1:n = 5, m = 5, a = 1, b = 2,奶酪 c = (1, 2, 4, 8, 16);5 条边:1–2 (4)、2–3 (3)、3–4 (1)、2–5 (2)、3–1 (8)。

结点 x猫的最短路W(x)含义
1(猫窝)原地不动0猫一开始就站在这儿
2(老鼠洞)1 → 2,长度 44猫 4 个时刻后到洞口
31 → 2 → 3 = 4 + 3 = 7 < 8(1 → 3 直连)7猫走 7
41 → 2 → 3 → 4 = 4 + 3 + 1 = 88猫走 8
51 → 2 → 5 = 4 + 2 = 66猫走 6
1
为什么必须先算 W

题目里"猫从猫窝出发到结点 x 的最短时间"就是一个标准的单源最短路

猫想怎么走近就怎么近,所以取的是 W(x) = dist(a, x)

老鼠则被绑在自己选的那条路径上——两者不是同一个量

W = (0, 4, 7, 8, 6)

2
一个立刻能看出的结论

W(a) = 0,而老鼠站在 a 上时"到 a 的时刻"是 0

要求 0 < W(a) = 0 不成立

所以 猫窝自身永远不是安全结点

A(a) 一定是负数

🧮 第 ② 步:从老鼠洞 b = 2 出发,用大根堆倒推 A(x)

递推式(w(x, y) 是 x 与 y 之间的边权):

A(b) = W(b) − 1  A(x) = min( W(x) − 1, max邻居 y ( A(y) − w(x, y) ) )

1
洞口先定稿:A(2) = W(2) − 1 = 3

老鼠在洞里只要"猫还没到"就安全

整数时刻下 3 < 4 = W(2) 成立,4 < 4 不成立

所以最晚能安全待在第 3 个时刻

A(2) = 3

2
从 2 向外扩一圈(3 个邻居)

邻居 3(边权 3):cand = min(W(3) − 1, A(2) − 3) = min(6, 0) = 0

邻居 5(边权 2):cand = min(W(5) − 1, A(2) − 2) = min(5, 1) = 1

邻居 1(边权 4):cand = min(W(1) − 1, A(2) − 4) = min(−1, −1) = −1

A(3) = 0,A(5) = 1,A(1) = −1

3
堆顶最大的是 A(5) = 1 → 定稿

5 的唯一邻居是 2,而 2 已经定稿

没有更优的扩展,直接结束

A(5) = 1 定稿

4
下一个堆顶 A(3) = 0 → 定稿,继续外扩

邻居 4(边权 1):cand = min(W(4) − 1, A(3) − 1) = min(7, −1) = −1

邻居 1(边权 8):cand = min(W(1) − 1, A(3) − 8) = min(−1, −8) = −8,不更优

邻居 2 已定稿

A(4) = −1

5
剩下的 A(1) = −1、A(4) = −1 依次弹出

从 1 出发看 3:min(W(3) − 1, A(1) − 8) = min(6, −9) = −9,不更优

从 4 出发看 3:min(W(3) − 1, A(4) − 1) = min(6, −2) = −2,不更优

负值只会越扩越小,扩散自然停止

所有点的 A 值都定稿了

结点 xW(x)A(x)A(x) ≥ 0?奶酪 cᵢ
10−1❌ 不安全1
243✅ 安全2
370✅ 安全4
48−1❌ 不安全8
561✅ 安全16

安全问题:2 + 4 + 16 = 22 ✓

🔑
注意 A(3) = 0 这个"刚好安全"的点:
老鼠从 3 出发,先花 3 个时刻走到 2(时刻 3 到洞),而猫要 4 个时刻才到 2——3 < 4,赢了 1 个时刻。
换条路 3 → 4 → … 呢?到 4 要 1 个时刻,猫到 4 要 8 个时刻,但再从 4 回 2 还得 1 + 3 = 4 个时刻,到 2 时已是时刻 4,4 < 4 不成立,被抓。
所以"路口的每一站"都要检查,不能只看终点。

🧮 反例:W(4) = 8 看着很"安全",实际不安全

结点 4 离猫很远(猫要 8 个时刻),离洞口也只隔一条边,但它并不安全。

老鼠的路线到 4到 3到 2结论
4 → 3 → 20(起点)1(猫 7 > 1 ✓)4(猫 4 > 4 ✗)第 3 站被抓
4 → 3 → 1 → 2011 + 8 = 9(猫 4 ✗)绕路更慢,必被抓
1
正确的直觉:安全是"整条路都对",不是"某一站对"

老鼠要么在最后一刻冲进洞,要么在某一站被猫截住

A(4) = −1 的含义是:老鼠必须比现在提前 1 个时刻出发才有希望

可现实里老鼠就是时刻 0 出发,所以 4 号点拿不到

A(4) = −1 < 0 → 不安全

2
顺带看清样例 2(6 个点全是 1 分奶酪)

W = (4, 3, 0, 5, 8, 6),所以 A = (−5, −4, −1, 4, 1, 3)

A ≥ 0 的点只有 4、5、6 三个,答案是 3 ✓

5 的额度 1 来自"5 → 4 只有 1 步";6 的额度 3 来自"6 → 4 一条边直达"

题干里 3 2 4 这条平行边和 3 3 6 这个自环都无害:平行边取更短的(W(2) = 3),自环永远只会让自己更差

样例 2 答案 3 ✓

⚠️
两个必须记住的坑:① 老鼠的时间是"沿它自己选的那条路径"算的,不能用"老鼠到 x 的最短路",否则会算出偏乐观的答案;② A(x) 是"最大化最小值"的瓶颈量,把它当成普通最短路用 SPFA / Bellman-Ford 求最长路会写错语义(还会因为环的存在而不收敛),正解是"每次取当前 A 值最大的点定稿"的大根堆扩张。
04
解法对比
大根堆瓶颈递推 vs 迭代松弛(Bellman-Ford 式) vs 朴素暴力

⚔️ 解法对比

🟢 大根堆 + 瓶颈递推(推荐) 推荐

先跑 Dijkstra 得 W(x),再把 A 的递推式当成"最大化最小值"的 Dijkstra:每轮取 A 最大的点定稿

  • 时间 O((n + m) log n)
  • 两遍类 Dijkstra,常数很小
  • 代码约 60 行
  • n = m = 10⁵ 轻松过
💡
正确性来源:任何一条从 x 到 b 的路径的价值 = min(沿途各站 W(y) − 已走距离 − 1);沿着路径往前走,这个"最小值"只会变小。
于是"当前 A 值最大的点"不可能再被别的点改善(否则那个点先出堆),它一定是最终值——与 Dijkstra 的贪心证明完全同构。

🟠 迭代松弛(Bellman-Ford 式)

把 A(x) 的递推式反复代入,直到一整轮都没有更新为止

  • 时间 O(n m)
  • 代码更短、更好想
  • n = m = 10⁵ 时约 10¹⁰
  • 会超时
⚠️
它为什么不快:每次迭代只能把"正确的 A 值"往外传播一条边,最长要 n 轮才收敛,
而堆版本一次就把当前最优的点定稿,每点只被扩展一次。两者算的是同一个值,只是效率差一个量级。

📈 性能对比

方案复杂度代码量
大根堆瓶颈递推O((n + m) log n)✅ 正解,约 60 行
迭代松弛(BF 式)O(n m)⭕ 正确但会超时,约 30 行
枚举所有简单路径指数级❌ 只能验证小数据,约 25 行
05
算法流程图
两遍类 Dijkstra:一遍算猫,一遍倒推老鼠的额度
开始读入 n、m、a、b、cᵢ 与 m 条边 (u, v, w)以猫窝 a 为源跑 Dijkstra,得到 W(x)A(b) = W(b) − 1;其余点的 A 先记为 −∞大根堆初始化:把 (A(b), b) 压入堆堆非空吗?是 ✓弹出 A 值最大的点 u否 ✗递推结束u 的 A 值已经不可能再被改善,标记为已定稿枚举 u 的每个邻居 v(边权 w):cand = min(W(v) − 1, A(u) − w)cand 比当前的 A(v) 更大吗?是 ✓更新 A(v) 并入堆否 ✗这条边不改动把所有 A(u) ≥ 0 的结点的 cᵤ 相加输出回到堆顶取下一个
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🛡️ 安全结点计算器(W、A 一表看清)

第 1 行输入 n m;第 2 行输入 a b;第 3 行输入 n 个奶酪价值;随后 m 行每行 u v w。程序会算出猫的时间 W(x)、老鼠的额度 A(x),并标出哪些点安全。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(两遍类 Dijkstra)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF  =  4e18;      // 正无穷:给猫的最短路用
const ll NEG  = -4e18;      // 负无穷:给老鼠的额度用

int n, m, a, b;
vector< pair<int, ll> > g[100005];
ll c[100005], W[100005], A[100005];
bool fin[100005];

int main() {
    scanf("%d %d", &n, &m);
    scanf("%d %d", &a, &b);
    for (int i = 1; i <= n; i++) scanf("%lld", &c[i]);
    for (int i = 0; i < m; i++) {
        int u, v; ll w;
        scanf("%d %d %lld", &u, &v, &w);
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }

    // ---------- ① 猫到每个点的最短时间 W(x) ----------
    for (int i = 1; i <= n; i++) W[i] = INF;
    priority_queue< pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll, int> > > pq;
    W[a] = 0;
    pq.push(make_pair(0, a));
    while (!pq.empty()) {
        ll d = pq.top().first;
        int x = pq.top().second;
        pq.pop();
        if (d > W[x]) continue;               // 过期状态丢掉
        for (int t = 0; t < (int)g[x].size(); t++) {
            int y  = g[x][t].first;
            ll  w  = g[x][t].second;
            if (d + w < W[y]) {
                W[y] = d + w;
                pq.push(make_pair(W[y], y));
            }
        }
    }

    // ---------- ② 老鼠的额度 A(x):大根堆,从 b 往外扩张 ----------
    for (int i = 1; i <= n; i++) A[i] = NEG;
    A[b] = W[b] - 1;                          // 洞里的最后一刻:W(b)-1 < W(b)

    priority_queue< pair<ll, int> > hp;        // 默认就是大根堆,取 A 最大的点
    hp.push(make_pair(A[b], b));

    while (!hp.empty()) {
        ll av = hp.top().first;
        int x = hp.top().second;
        hp.pop();
        if (fin[x]) continue;
        if (av < A[x]) continue;               // 只处理最新版本
        fin[x] = true;                         // 弹出来就是最终值

        for (int t = 0; t < (int)g[x].size(); t++) {
            int y = g[x][t].first;
            ll  w = g[x][t].second;
            if (fin[y]) continue;              // 已定稿的点不用再改
            ll cand = min(A[x] - w, W[y] - 1); // 先赶到 y,再保证站在 y 上猫还没来
            if (cand > A[y]) {
                A[y] = cand;
                hp.push(make_pair(cand, y));
            }
        }
    }

    // ---------- ③ 统计所有 A(u) >= 0 的奶酪 ----------
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        if (A[i] >= 0) ans += c[i];

    printf("%lld\n", ans);
    return 0;
}
🔑
三个要点:① 两遍 Dijkstra 的"优先级方向"刚好相反:猫那一遍取最小(小根堆),老鼠这一遍取最大(大根堆);② A(b) = W(b) - 1,这里的 -1 就是"严格大于"在整数世界里的代价;③ W[y] - 1 这个上限必须留在 min 里面——它表示"站在 y 上时猫还没到",漏掉就变成了"只看能不能连到 b"。

📖 关键几行怎么看

代码作用为什么这样写
if (fin[y]) continue;跳过已定稿的点已定稿的 A 值不会再变,重复更新纯属浪费
ll cand = min(A[x] - w, W[y] - 1);候选额度先走到 y(额度 −w),再要求 y 这一站也安全
if (cand > A[y])取最大瓶颈型问题要的是"最好的一次机会",越大越好
priority_queue<pair<ll,int> > hp;大根堆默认比较就是"先比 first 再比 second",正好按 A 值排序
if (A[i] >= 0) ans += c[i];判定 + 累加A(i) ≥ 0 等价于"时刻 0 从 i 出发就安全"
long long 全用一遍防溢出W 和 A 可达 10⁵ × 10⁹ = 10¹⁴;奶酪和也可达 10¹⁴
⚠️
五个坑:① 把老鼠的时间写成"老鼠的最短路"(应为沿所选路径的时间);② 忘记把严格不等式换成 −1,答案会偏大;③ 两遍都用小根堆(或都用大根堆),语义直接反掉;④ 更新时漏掉 min(..., W[y] - 1),会把"猫早就到过的点"也算成安全;⑤ 用 int 存 W、A 或答案(10¹⁴ 溢出)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5 5
1 2
1 2 4 8 16
1 2 4
2 3 3
3 4 1
2 5 2
3 1 8
22题面样例 1(安全点 2、3、5,2+4+16)
6 10
3 4
1 1 1 1 1 1
1 2 6
2 3 3
3 1 4
3 4 5
4 5 8
5 6 2
6 4 1
3 2 4
5 4 4
3 3 6
3题面样例 2(安全点 4、5、6;含平行边与自环)
2 1
1 2
5 7
1 2 3
7n 最小:猫窝自身不安全,只有老鼠洞安全
3 3
2 3
10 20 30
2 3 1
1 2 1
1 3 4
30W(a) = 0:猫窝一侧(1、2)全都拿不到
3 2
1 3
1 1 1
1 2 1
2 3 1
2链式路径:2 与 3 安全,1 不安全
4 5
1 4
1000000000 1000000000 1000000000 1000000000
1 2 2
2 4 2
1 3 100
3 4 100
4 4 1
2000000000大价值累加(必须 long long)+ 自环无害
✅
自查清单:① 跑了 Dijkstra 得到 W 吗?② A(b) 用的是 W(b) − 1 吗?③ 递推是 min(W(v)−1, A(u)−w) 吗?④ 用的是大根堆吗?⑤ 统计条件写的是 A(u) ≥ 0 吗?

🚨 易错点清单

⚠️
把"严格大于"漏成"大于等于":猫到达时刻恰好等于老鼠到达时刻时老鼠会被抓,必须减 1 变成 ≤。
⚠️
把老鼠的时间当成最短路:老鼠只能沿它自己选的那条路径走,不能用 dist(u, x) 代替路径距离。
⚠️
堆的方向反了:A 是"最大化最小值"的瓶颈量,必须用大根堆,用小根堆会先定稿一个偏小的值。
⚠️
忘记 W(x) − 1 这个上限:只做邻居递推会认为"能连到 b 就安全",把猫的下班时间忘光了。
⚠️
用 int:W、A 与总和都能到 10¹⁴,必须 long long。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O((n + m) log n)
空间复杂度
O(n + m)
堆操作次数
每点最多入堆 O(m) 次
数据规模
n, m ≤ 10⁵

时间怎么算的?

空间都用在哪?

邻接表存 2m 条有向边(无向边拆两条)O(n + m);额外只有 W、A、c、fin 四个长度 n + 1 的数组。

✅ 两遍类 Dijkstra,线性级内存,n = m = 10⁵ 的正解复杂度。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「瓶颈型最短路」(最大化最小值 / 最小化最大值)通用模板
// 1) 先把手算得出来的"上限"变成点权:本题 upper[x] = W[x] - 1
// 2) 定义 dp[x] = 在 x 上还"撑得住"的最大值
// 3) 从"已知最好的点"出发,用【大根堆】每次取 dp 最大的点定稿
//    扩展时 cand = min( dp[u] - w, upper[v] )    <- 先减消耗,再卡上限
// 4) 若题意是"最小化最大值",就把大根堆换成小根堆、min 换成 max,形状完全一样

priority_queue< pair<ll,int> > hp;   // 大根堆:按 dp 值从大到小
hp.push(make_pair(dp[s], s));
while (!hp.empty()) {
    ll dv = hp.top().first; int u = hp.top().second; hp.pop();
    if (done[u]) continue;
    done[u] = true;                  // 定稿
    for (每条边 u -> v,权 w) {
        ll cand = min(dp[u] - w, upper[v]);
        if (cand > dp[v]) { dp[v] = cand; hp.push(make_pair(cand, v)); }
    }
}

// 严格不等式的通用处理:整数世界里 a > b  ⟺  a ≥ b + 1
// 所以"猫比老鼠晚到" ⟺ "老鼠的时刻 ≤ 猫的时刻 - 1"
// 这个 -1 一旦漏掉,边界(恰好同时到达)就会判错

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
单源最短路(Dijkstra)一遍算出猫到每个点的最短时间 W(x)任何"两个玩家/两个时刻表"的比较题
瓶颈 / 最大最小A(x) = min(W(x)−1, max(A(y)−w))最大生成树(最小边最大)、最小瓶颈路、最宽路径
反向扩张从终点 b 出发倒推每个点的"额度"倒推可行性、反向 DP、撤离/追及问题
严格不等式转 ≤W(x) > t + d ⟺ t + d ≤ W(x) − 1所有"必须严格早/严格小于"的整数问题
大根堆定稿每轮取 A 最大的点,弹出即最终值任何满足"扩张后只会变差"的贪心可证明问题
🌟
思考题:如果改成"老鼠从 u 出发时已经提前"t₀ 个时刻(即它在时刻 −t₀ 就出发了),哪些点会变成安全?(提示:只需把输出条件从 A(u) ≥ 0 换成 A(u) ≥ −t₀,整套算法一行都不用改——因为 A(u) 的物理含义本来就是"最多能提前多久出发"。把"提前量"当成阈值去卡,是这类题最省力的推广方式。)