C++算法
C++ 算法题解析：猫和老鼠（最短路与安全路径判定）
本文解析 C++ 编程题“猫和老鼠”。题目要求在无向图中，判断哪些节点是安全的。安全定义为从该节点到终点（老鼠洞）的最短时间严格小于起点（猫窝）到终点的最短时间。解决方案采用 Dijkstra 算法，以老鼠洞为起点计算单源最短路，比较各点到洞的距离与猫到洞的距离，累加安全节点上的奶酪价值。
本文解析 C++ 编程题“猫和老鼠”。题目要求在无向图中，判断哪些节点是安全的。安全定义为从该节点到终点（老鼠洞）的最短时间严格小于起点（猫窝）到终点的最短时间。解决方案采用 Dijkstra 算法，以老鼠洞为起点计算单源最短路，比较各点到洞的距离与猫到洞的距离，累加安全节点上的奶酪价值。
| 角色 | 位置 |
|---|---|
| 猫 | 猫窝（起点 A） |
| 老鼠 | 某个点出发 |
| 老鼠洞 | 终点 B |
一个结点是 安全的，当且仅当： 老鼠能规划一条 从该结点到老鼠洞的路径， 使得： 路径上任意结点 v（包括起点和终点） 👉 猫到 v 的最短时间 👉 严格大于 👉 老鼠从 v 到老鼠洞的时间
在任何一个地方：
如果在路上 每一个地方 都是：
🐭 比 🐱 快
那老鼠就 绝对安全 ✅
在这道题里，
老鼠的路程只考虑'从某个点 → 老鼠洞 b'这一条方向
对于每一个点 i：
谁更快？
老鼠站在某个结点 i 上，如果满足以下条件，就叫 安全结点：
老鼠从 i 出发，能规划一条逃到洞 b 的路线， 并且在这条路线上的任何地方，猫都'追不上'老鼠
对路径上的任意结点 j：
猫从猫窝 a → j 的最短时间 > 老鼠从 j → 老鼠洞 b 的时间
📌 猫必须严格更慢（大于）！
老鼠的规则是：
从 任何点 i，都要能跑到 洞 b
所以我们干脆：
📌 这一步，用的就是：
Dijkstra 最短路算法
dis[i] = 从结点 i 到老鼠洞的最短时间
注意： 图是无向图 👉 从 i 到 b 👉 等价于从 b 到 i
对于路径上任意结点 j： 猫从猫窝出发到结点 j 的最短时间 严格大于 老鼠从 j 沿这条路径前往老鼠洞的时间
注意这里有两个'到'：
这句话乍一看，好像我们必须知道：
猫从 a 到'每一个 j'的最短时间
对不对？ 表面上是的。
这里需要数学逻辑。
因为本题考虑的是单向行程，老鼠选择的是一条 从 i 回洞 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
比较：
2 < 5 ✅
👉 老鼠一定比猫快 👉 C 是安全点
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; }
🐭 老鼠要算到洞路 🐱 猫猫一路追到洞 🧀 鼠比猫快就安全 ➕ 安全奶酪全拿走
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online