C++ 算法题解析：猫和老鼠（最短路与安全路径判定）

对于每一个点 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 不安全

知识点总结

本题叫《猫和老鼠》， 但在算法里，它是：

🧠 单源最短路 + 安全性判定

用到的核心知识：

代码实现

#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; }

总结

🐭 老鼠要算到洞路 🐱 猫猫一路追到洞 🧀 鼠比猫快就安全 ➕ 安全奶酪全拿走