猫和老鼠 题解

题目分析

本题描述了一个猫追老鼠的场景。图上有 $n$ 个结点和 $m$ 条带权无向边，猫位于结点 $a$，老鼠洞位于结点 $b$。老鼠想从某个结点 $u$ 出发，沿着某条路径逃回老鼠洞 $b$。如果在整条路径上的任意一个结点 $x$（含 $u$ 和 $b$），猫从 $a$ 到 $x$ 的最短时间都严格大于老鼠从 $u$ 沿该路径到 $x$ 的时间，则结点 $u$ 是安全的。老鼠只能拿取安全结点的奶酪，求安全结点的奶酪价值总和。

初看条件非常复杂，但通过分析可以将其转化为简洁的最短路比较问题。

解题思路

1. 形式化定义

设 $dist(x,y)$ 表示图中 $x$ 到 $y$ 的最短时间。
猫从 $a$ 到达 $x$ 的最短时间为 $dist(a, x)$。

对于结点 $u$，老鼠若选择某条路径 $P: u = v_0 \to v_1 \to \dots \to v_k = b$，令 $mouse(v_i)$ 表示老鼠从 $u$ 出发沿 $P$ 到达 $v_i$ 的时间（即路径前缀长度）。安全条件为：

由于 $mouse(v_i)$ 一定大于等于最短距离 $dist(u, v_i)$，因此如果存在路径 $P$ 满足条件，则必然有 $dist(a,v_i)>dist(u,v_i)$。特别地，取终点 $v_k=b$，有：

由此得到必要条件：$dist(u,b)<dist(a,b)$。

2. 必要也是充分

我们证明：只要 $dist(u,b)<dist(a,b)$，老鼠沿 $u$ 到 $b$ 的最短路径逃跑，就一定能满足安全条件。

假设老鼠选择最短路路径，则对于路径上的任意结点 $x$，有 $dist(u,x) = dist(u,b) - dist(x,b)$。我们需要验证 $dist(a,x)>dist(u,x)$。用反证法：

若存在某个 $x$ 使得 $dist(a,x) \le dist(u,x)$，则由三角不等式：

这与 $dist(u,b)<dist(a,b)$ 矛盾。

因此，结点 $u$ 安全 $⟺dist(u,b)<dist(a,b)$。问题转化为：以 $b$ 为源点求单源最短路，找出所有满足 $dist(u,b)<dist(a,b)$ 的结点，将其奶酪价值累加。

算法说明

整体流程分为三步：

1. 建图：使用邻接表存储无向边，边权为通过时间 $w_i$。
2. 最短路：从老鼠洞 $b$ 出发，运行 Dijkstra 算法求出到所有结点的最短距离 $dis[u] = dist(b, u)$。
3. 统计答案：遍历所有结点 $i$，若 $dis[i]<dis[a]$，则累加 $c_i$。这里 $dis[a] = dist(b,a) = dist(a,b)$。

为什么从 $b$ 出发？

因为我们要比较的是 $dist(u,b)$ 和 $dist(a,b)$ 的大小，从 $b$ 出发可以一次性求出所有点到 $b$ 的距离。由于图是无向图，$dist(b, u) = dist(u, b)$。

时间复杂度分析

• 图的边数 $m \le 10^5$，结点数 $n \le 10^5$。
• Dijkstra 算法使用优先队列实现，时间复杂度为 $O((n+m)\log n)$，在题目限制内可以高效运行。

参考代码

以下是题目给出的 C++ 参考代码，加上了详细注释。

cpp
复制
1#include <cstdio>
2#include <algorithm>
3#include <vector>
4#include <queue>
5using namespace std;
6
7const int N = 1e5 + 5;
8const long long oo = 1e18;          // 定义一个很大的数作为无穷大
9
10int n, m;
11int a, b;
12int c[N];
13vector<pair<int, int>> e[N];        // 邻接表，pair<邻接点, 边权>
14long long dis[N];                   // 各点到 b 的最短距离
15priority_queue<pair<long long, int>> q; // 小根堆优化 Dijkstra
16long long ans;
17
18int main() {
19    scanf("%d%d", &n, &m);
20    scanf("%d%d", &a, &b);
21    for (int i = 1; i <= n; i++)
22        scanf("%d", &c[i]);
23    for (int i = 1; i <= m; i++) {
24        int u, v, w;
25        scanf("%d%d%d", &u, &v, &w);
26        e[u].emplace_back(make_pair(v, w)); // 事实上可直接用 e[u].emplace_back(v, w)
27        e[v].emplace_back(make_pair(u, w));
28    }
29
30    // 初始化距离数组
31    for (int i = 1; i <= n; i++)
32        dis[i] = oo;
33    dis[b] = 0;
34    q.push(make_pair(-dis[b], b));  // 优先队列默认大根堆，取负变相实现小根堆
35
36    // Dijkstra 求最短路
37    while (!q.empty()) {
38        auto p = q.top();
39        q.pop();
40        // 惰性删除：跳过已经更新过距离的旧记录
41        if (dis[p.second] != -p.first)
42            continue;
43        int u = p.second;
44        for (auto r : e[u]) {
45            int v = r.first, w = r.second;
46            if (dis[v] > dis[u] + w) {
47                dis[v] = dis[u] + w;
48                q.push(make_pair(-dis[v], v));
49            }
50        }
51    }
52
53    // 统计答案：所有 dis[i] < dis[a] 的点都是安全的
54    for (int i = 1; i <= n; i++)
55        if (dis[i] < dis[a])
56            ans += c[i];
57
58    printf("%lld\n", ans);
59    return 0;
60}

代码解释

• 邻接表存储：vector<pair<int,int>> e[N]，每个元素是 (v, w)，表示一条 $u$-$v$ 权值为 $w$ 的边。采用 emplace_back / push_back 添加双向边。
• Dijkstra 实现：用 priority_queue 维护待扩展结点，存储 (-dis, u)，通过取负数快速实现小根堆。取出堆顶后判断当前距离是否已被更新，若不是则跳过（惰性删除）；否则松弛邻边。
• 无穷大：oo 取值 $10^{18}$，因为最大边权 $10^9$ 且结点数 $10^5$，最远距离不超过 $10^{14}$，使用 $10^{18}$ 安全。
• 答案累加：ans 使用 long long 类型，因为奶酪价值 $c_i$ 最大可达 $10^9$，$n$ 个累加可能超过 int 范围。

注意事项

1. 数据范围较大，务必使用 long long 存储距离和最终答案。
2. 图是无向的，输入边时要建双向边。
3. 采用优先队列优化的 Dijkstra 时，记得进行惰性删除，避免重复搜索造成效率下降。
4. 条件中的“严格大于”最终转化为严格小于号 dis[i] < dis[a]，注意不能取等号。