先用 Dijkstra 算出猫到每个点的时间 W(x),再从老鼠洞出发,用"大根堆 + 瓶颈递推"倒推每个点最晚能安全出发的时刻 A(x)。
猫和老鼠所在的庄园是一张由 n 个点、m 条带权无向边组成的连通图。结点 i 上放有价值 cᵢ 的奶酪;第 i 条边连接 uᵢ 与 vᵢ,边权 wᵢ 表示猫或老鼠通过这条边需要的时间。
猫窝在结点 a,老鼠洞在结点 b。对于老鼠而言,结点 u 是安全的当且仅当:老鼠能规划一条从 u 出发逃往老鼠洞的路径,使得对于路径上的任意结点 x(包含起点 u 与终点 b)都有:猫从猫窝出发到 x 的最短时间 严格大于老鼠从 u 沿这条路径走到 x 所需的时间。
老鼠只敢拿安全结点上的奶酪,求它能拿到的奶酪价值之和。
| 样例 | 输入 | 输出 |
|---|---|---|
| 样例 1 | 5 5 | 22 |
| 样例 2 | 6 10 | 3 |
u,挑一条通往 b 的路,路上每一个落脚点都得满足"我到得比猫早"。≤,后面就能用整数递推了。安全结点判定瓶颈型最短路最大程度松弛大根堆 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 |
x 定义 A(x):"老鼠在时刻 t 站在 x 上还能安全逃到 b"所允许的最大 t。那么"u 安全" ⟺ A(u) ≥ 0b 倒着推:A(b) = W(b) − 1(在洞里的最后一刻猫还没到);其它点 A(x) = min(W(x) − 1, max_{邻居 y} (A(y) − w(x, y)))——先要求"站在 x 上时猫还没到",再要求"能从某个邻居安全地继续走"A 值最大的点定稿,与 Dijkstra 取最小的点刚好相反n = m = 10⁵、cᵢ 最大 10⁹ 时总和可达 10¹⁴,必须用 long long样例 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,长度 4 | 4 | 猫 4 个时刻后到洞口 |
| 3 | 1 → 2 → 3 = 4 + 3 = 7 < 8(1 → 3 直连) | 7 | 猫走 7 |
| 4 | 1 → 2 → 3 → 4 = 4 + 3 + 1 = 8 | 8 | 猫走 8 |
| 5 | 1 → 2 → 5 = 4 + 2 = 6 | 6 | 猫走 6 |
题目里"猫从猫窝出发到结点 x 的最短时间"就是一个标准的单源最短路
猫想怎么走近就怎么近,所以取的是 W(x) = dist(a, x)
老鼠则被绑在自己选的那条路径上——两者不是同一个量
W = (0, 4, 7, 8, 6)
W(a) = 0,而老鼠站在 a 上时"到 a 的时刻"是 0
要求 0 < W(a) = 0 不成立
所以 猫窝自身永远不是安全结点
A(a) 一定是负数
递推式(w(x, y) 是 x 与 y 之间的边权):
A(b) = W(b) − 1 A(x) = min( W(x) − 1, max邻居 y ( A(y) − w(x, y) ) )
老鼠在洞里只要"猫还没到"就安全
整数时刻下 3 < 4 = W(2) 成立,4 < 4 不成立
所以最晚能安全待在第 3 个时刻
A(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
5 的唯一邻居是 2,而 2 已经定稿
没有更优的扩展,直接结束
A(5) = 1 定稿
邻居 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
从 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 值都定稿了
| 结点 x | W(x) | A(x) | A(x) ≥ 0? | 奶酪 cᵢ |
|---|---|---|---|---|
| 1 | 0 | −1 | ❌ 不安全 | 1 |
| 2 | 4 | 3 | ✅ 安全 | 2 |
| 3 | 7 | 0 | ✅ 安全 | 4 |
| 4 | 8 | −1 | ❌ 不安全 | 8 |
| 5 | 6 | 1 | ✅ 安全 | 16 |
安全问题:2 + 4 + 16 = 22 ✓
3 → 4 → … 呢?到 4 要 1 个时刻,猫到 4 要 8 个时刻,但再从 4 回 2 还得 1 + 3 = 4 个时刻,到 2 时已是时刻 4,4 < 4 不成立,被抓。结点 4 离猫很远(猫要 8 个时刻),离洞口也只隔一条边,但它并不安全。
| 老鼠的路线 | 到 4 | 到 3 | 到 2 | 结论 |
|---|---|---|---|---|
| 4 → 3 → 2 | 0(起点) | 1(猫 7 > 1 ✓) | 4(猫 4 > 4 ✗) | 第 3 站被抓 |
| 4 → 3 → 1 → 2 | 0 | 1 | 1 + 8 = 9(猫 4 ✗) | 绕路更慢,必被抓 |
老鼠要么在最后一刻冲进洞,要么在某一站被猫截住
A(4) = −1 的含义是:老鼠必须比现在提前 1 个时刻出发才有希望
可现实里老鼠就是时刻 0 出发,所以 4 号点拿不到
A(4) = −1 < 0 → 不安全
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 ✓
A(x) 是"最大化最小值"的瓶颈量,把它当成普通最短路用 SPFA / Bellman-Ford 求最长路会写错语义(还会因为环的存在而不收敛),正解是"每次取当前 A 值最大的点定稿"的大根堆扩张。先跑 Dijkstra 得 W(x),再把 A 的递推式当成"最大化最小值"的 Dijkstra:每轮取 A 最大的点定稿
min(沿途各站 W(y) − 已走距离 − 1);沿着路径往前走,这个"最小值"只会变小。把 A(x) 的递推式反复代入,直到一整轮都没有更新为止
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 大根堆瓶颈递推 | O((n + m) log n) | ✅ 正解,约 60 行 |
| 迭代松弛(BF 式) | O(n m) | ⭕ 正确但会超时,约 30 行 |
| 枚举所有简单路径 | 指数级 | ❌ 只能验证小数据,约 25 行 |
第 1 行输入 n m;第 2 行输入 a b;第 3 行输入 n 个奶酪价值;随后 m 行每行 u v w。程序会算出猫的时间 W(x)、老鼠的额度 A(x),并标出哪些点安全。
点按钮开始 →
#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; }
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¹⁴ 溢出)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 5 | 22 | 题面样例 1(安全点 2、3、5,2+4+16) |
6 10 | 3 | 题面样例 2(安全点 4、5、6;含平行边与自环) |
2 1 | 7 | n 最小:猫窝自身不安全,只有老鼠洞安全 |
3 3 | 30 | W(a) = 0:猫窝一侧(1、2)全都拿不到 |
3 2 | 2 | 链式路径:2 与 3 安全,1 不安全 |
4 5 | 2000000000 | 大价值累加(必须 long long)+ 自环无害 |
W(b) − 1 吗?③ 递推是 min(W(v)−1, A(u)−w) 吗?④ 用的是大根堆吗?⑤ 统计条件写的是 A(u) ≥ 0 吗?≤。dist(u, x) 代替路径距离。W(x) − 1 这个上限:只做邻居递推会认为"能连到 b 就安全",把猫的下班时间忘光了。O((n + m) log n)O((n + m) log n)3 × 10⁶ 次堆操作,1 秒内非常宽裕邻接表存 2m 条有向边(无向边拆两条)O(n + m);额外只有 W、A、c、fin 四个长度 n + 1 的数组。
✅ 两遍类 Dijkstra,线性级内存,n = m = 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) 的物理含义本来就是"最多能提前多久出发"。把"提前量"当成阈值去卡,是这类题最省力的推广方式。)