题目描述
题目解析
问题背景
庄园模型
- 每个地点 = 一个点（结点）
- 每条小路 = 一条边
- 路上走要花时间 = 边权
角色设定
| 角色 | 位置 |
|---|---|
| 猫 | 猫窝（起点 A） |
| 老鼠 | 某个点出发 |
| 老鼠洞 | 终点 B |
规则说明
- 每个点上可能有奶酪，奶酪有价值。
- 老鼠想拿奶酪，但怕被猫抓。
安全结点定义
核心条件
一个结点是 安全的，当且仅当： 老鼠能规划一条 从该结点到老鼠洞的路径， 使得： 路径上任意结点 v（包括起点和终点） 👉 猫到 v 的最短时间 👉 严格大于 👉 老鼠从 v 到老鼠洞的时间
通俗理解
在任何一个地方：
- 🐭 老鼠 跑到洞里
- 🐱 猫 追过来
如果在路上 每一个地方 都是：
🐭 比 🐱 快
那老鼠就 绝对安全 ✅
单向路程说明
在这道题里，
老鼠的路程只考虑'从某个点 → 老鼠洞 b'这一条方向
- ❌ 不考虑：洞 → 点 → 洞
- ✅ 只考虑：点 → 洞
算法思路
核心问题
对于每一个点 i：
- 猫到 i 的最短时间
- 老鼠从 i 到洞的最短时间
谁更快？
安全结点判定
老鼠站在某个结点 i 上，如果满足以下条件，就叫 安全结点：
老鼠从 i 出发，能规划一条逃到洞 b 的路线， 并且在这条路线上的任何地方，猫都'追不上'老鼠
时间判断逻辑
对路径上的任意结点 j：
猫从猫窝 a → j 的最短时间 > 老鼠从 j → 老鼠洞 b 的时间
📌 猫必须严格更慢（大于）！
步骤一：计算老鼠到洞的最短路
反向计算原因
老鼠的规则是：
从 任何点 i，都要能跑到 洞 b
所以我们干脆：
- 把 老鼠洞 b 当起点
- 计算： 👉 b 到所有点的最短路
📌 这一步，用的就是：
Dijkstra 最短路算法
结果含义
dis[i] = 从结点 i 到老鼠洞的最短时间
注意： 图是无向图 👉 从 i 到 b 👉 等价于从 b 到 i
步骤二：猫的时间判定
关键句翻译
对于路径上任意结点 j： 猫从猫窝出发到结点 j 的最短时间 严格大于 老鼠从 j 沿这条路径前往老鼠洞的时间
注意这里有两个'到'：
- 猫：a → j
- 老鼠：j → b
这句话乍一看，好像我们必须知道：
猫从 a 到'每一个 j'的最短时间
对不对？ 表面上是的。
优化逻辑
这里需要数学逻辑。
关键观察
因为本题考虑的是单向行程，老鼠选择的是一条 从 i 回洞 b 的路径。在这条路径上：
- 老鼠从 j 到 b 的时间 =
👉
dis[j]（最短路）
而猫想抓住老鼠，追逐的终点是哪里？**
追逐终点
答案：追逐的终点 —— 老鼠洞 b
原因很重要：
- 老鼠一路跑，时间越来越少
- 猫一路追，距离老鼠洞，越来越短
- 最危险的点，恰恰是老鼠即将成功的那一刻
也就是：
老鼠到达洞 b 的那一刻
核心推理
如果：
猫到洞的最短时间 > 老鼠到洞的最短时间
那么说明：老鼠已经进洞了猫连'终点'都到不了那么在 路上的任何一个 j猫更不可能提前赶到
📌 终点都追不上，中途更不可能追上，因为本题规定的就是单向的追逐，没有中间伏击的可能！
步骤三：统计结果
程序最后做的事非常简单：
for (int i = 1; i <= n; i++) if (dis[i] < dis[a]) ans += c[i];
逻辑翻译
- 一个一个点看
- 如果这个点是 安全的
- 👉 把它的奶酪价值加起来
示例分析
假设场景
猫窝 A —— 5 分钟 —— 老鼠洞 B 点 C —— 2 分钟 —— 老鼠洞 B
分析点 C 安不安全？
- 🐭 老鼠： C → B 用 2 分钟
- 🐱 猫： A → B 用 5 分钟
比较：
2 < 5 ✅
👉 老鼠一定比猫快 👉 C 是安全点
分析点 D 安不安全？
D → B = 6 分钟 A → B = 5 分钟
6 < 5 ❌
👉 老鼠会被追上 👉 D 不安全
知识点总结
本题叫《猫和老鼠》， 但在算法里，它是：
🧠 单源最短路 + 安全性判定
用到的核心知识：
| 知识点 | 是否重要 |
|---|---|
| 图的建模 | ⭐⭐⭐ |
| Dijkstra | ⭐⭐⭐⭐ |
| 距离比较 | ⭐⭐⭐ |
| 转换题意 | ⭐⭐⭐⭐ |
代码实现
#include <cstdio> // scanf、printf，用来输入输出（速度快） #include <algorithm> // 算法工具（本题中备用） #include <vector> // vector：用来存图的边 #include <queue> // priority_queue：优先队列（最短路用） using namespace std; /* ========================= 一、常量与全局变量 ========================= */ // 最大结点数（根据题目数据范围） const int N = 1e5 + 5; // 一个非常大的数，表示'无穷远' const long long oo = 1e18; int n, m; // n：结点数，m：边数 int a, b; // a：猫窝结点编号，b：老鼠洞结点编号 int c[N]; // c[i]：第 i 个结点的奶酪价值 // 邻接表 // e[u] 中存的是若干个 (v, w) // 表示：u 和 v 之间有一条路，走这条路需要 w 时间 vector<pair<int, int>> e[N]; // dis[i]：从结点 i 到老鼠洞 b 的最短时间 // 注意：这是'i → b'的时间 long long dis[N]; // 优先队列（堆） // 存 (-距离，结点编号) // 用负号是因为 priority_queue 默认是大顶堆 priority_queue<pair<long long, int>> q; long long ans; // 最终答案：老鼠能安全拿到的奶酪总价值 /* ========================= 二、主函数 ========================= */ int main() { /* ---------- 1. 读入基本信息 ---------- */ scanf("%d%d", &n, &m); // 读入结点数和边数 scanf("%d%d", &a, &b); // 读入猫窝 a 和老鼠洞 b // 读入每个结点的奶酪价值 for (int i = 1; i <= n; i++) scanf("%d", &c[i]); /* ---------- 2. 建图（无向图） ---------- */ for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); // u 和 v 之间有一条路，时间是 w // 因为是无向图，所以要加两次 e[u].emplace_back(v, w); // u → v e[v].emplace_back(u, w); // v → u } /* ---------- 3. Dijkstra 初始化 ---------- */ // 一开始，认为所有点到老鼠洞的距离都'非常远' for (int i = 1; i <= n; i++) dis[i] = oo; // 老鼠洞 b 到自己，时间是 0 dis[b] = 0; // 把老鼠洞放进优先队列 q.push(make_pair(-dis[b], b)); /* ---------- 4. Dijkstra 主循环 ---------- */ // 目标：算出'所有点到老鼠洞 b 的最短时间' while (!q.empty()) { // 取出当前'到洞时间最小'的结点 auto p = q.top(); q.pop(); // 如果这个状态已经不是最新的（旧数据），就跳过 if (dis[p.second] != -p.first) continue; int u = p.second; // 当前处理的结点 // 遍历 u 的所有相邻结点 for (auto r : e[u]) { int v = r.first; // 相邻结点 int w = r.second; // u → v 这条路的时间 // 如果：通过 u 再走到 v // 能让 v 到洞的时间更短 if (dis[v] > dis[u] + w) { // 更新 v 到洞的最短时间 dis[v] = dis[u] + w; // 把 v 加入优先队列 q.push(make_pair(-dis[v], v)); } } } /* ---------- 5. 判断安全结点并统计答案 ---------- */ for (int i = 1; i <= n; i++) { // 如果老鼠从 i 到洞的最短时间 // 严格小于 // 猫从猫窝 a 到洞的最短时间 if (dis[i] < dis[a]) { // 说明结点 i 是安全的 // 老鼠可以放心拿这里的奶酪 ans += c[i]; } } /* ---------- 6. 输出结果 ---------- */ printf("%lld\n", ans); return 0; }
总结
🐭 老鼠要算到洞路 🐱 猫猫一路追到洞 🧀 鼠比猫快就安全 ➕ 安全奶酪全拿走
