564 字
3 分钟

P11280 - Jom & Terry 题解

2024-11-16
2024-11-16
浏览量 加载中...
Done

您已获得最佳的阅读体验!

题目地址:P11280

题目难度:普及/提高-

Terry 和 Jom 在一个 个点 条边的有“根”无向连通图上博弈(图的根为 ),遵循以下规则:

  • Terry 先手;
  • 两人轮流在图上移动,每次只能走一条边(也可以睡觉,啥都不干);
  • Terry 不能走到 Jom 所在的结点(我们认为只有 Terry 自投罗网时才会被抓到,即如果 Terry 先移动到结点 后 Jom 在同一回合也移动到 是合法的)。

每次询问给定 Terry 和 Jom 的起点 ,你需要回答 Terry 能否到达点

为了避免题面命名给个人理解带来的混乱,本题解将用“猫”(Jom)、“鼠”(Terry)来区分二者。

我们的目的是让鼠无论如何都能在猫之前到达 ,因此我们先考虑猫的最优策略——当猫使用最优策略都无法抓到鼠时,那必定有鼠必胜。

鼠的唯一目的地是 ,因此猫只需先到 点,然后等着它就好了。于是猫一定会沿着到根的最短路径前行,而鼠为了不被抓住也会沿着距离根最短的那条路径行进。我们只需在最开始预处理出每个节点到 的最短距离即可。预估时间复杂度是

注意不要把 TerryJom 搞混了;输出量较大,慎用 endl(时间膨胀一倍多)。

#include <bits/stdc++.h>
#define N 1000010
using namespace std;
struct Edge {
int to, ne;
} edges[N << 1];
int h[N], idx = 0;
int dep[N];
int n, m, r;
void add(int u, int v) {
idx++;
edges[idx].to = v;
edges[idx].ne = h[u];
h[u] = idx;
}
void bfs() {
queue<int> q;
q.push(r);
dep[r] = 0;
while (!q.empty()) {
int t = q.front();
q.pop();
for (int i = h[t]; ~i; i = edges[i].ne) {
int j = edges[i].to;
if (dep[j] > dep[t] + 1) {
dep[j] = dep[t] + 1;
q.push(j);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
memset(dep, 0x3f, sizeof dep);
memset(h, -1, sizeof h);
int q;
cin >> n >> m >> r;
while (m--) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
bfs();
cin >> q;
cout << "I'm here!" << endl;
while (q--) {
int a, b;
cin >> a >> b;
cout << (dep[a] <= dep[b] ? "Terry" : "Jom") << '\n';
}
return 0;
}

支持与分享

如果这篇文章对你有帮助,欢迎分享给更多人或赞助支持!

赞助
P11280 - Jom & Terry 题解
https://justpureh2o.cn/articles/11280/
作者
JustPureH2O
发布于
2024-11-16
许可协议
CC BY-NC-SA 4.0
最后更新于 2024-11-16,距今已过 469 天

部分内容可能已过时

评论区

Profile Image of the Author
JustPureH2O
穷方圆平直之情,尽规矩准绳之用
公告
JustPureH2O 的博客现已正式迁移至 Astro!原 Hexo 网站将移至 https://hexo.justpureh2o.cn/
音乐
封面

音乐

暂未播放

0:00 0:00
暂无歌词
分类
标签
站点统计
文章
100
分类
13
标签
55
总字数
373,208
运行时长
0
最后活动
0 天前

目录