移动端 Banners
564 字
3 分钟
P11280 - Jom & Terry 题解
Done
您已获得最佳的阅读体验!
题目地址:P11280
题目难度:普及/提高-
Terry 和 Jom 在一个
个点 条边的有“根”无向连通图上博弈(图的根为 ),遵循以下规则:
- Terry 先手;
- 两人轮流在图上移动,每次只能走一条边(也可以睡觉,啥都不干);
- Terry 不能走到 Jom 所在的结点(我们认为只有 Terry 自投罗网时才会被抓到,即如果 Terry 先移动到结点
后 Jom 在同一回合也移动到 是合法的)。 每次询问给定 Terry 和 Jom 的起点
,你需要回答 Terry 能否到达点 。
为了避免题面命名给个人理解带来的混乱,本题解将用“猫”(Jom)、“鼠”(Terry)来区分二者。
我们的目的是让鼠无论如何都能在猫之前到达
鼠的唯一目的地是
注意不要把 Terry 和 Jom 搞混了;输出量较大,慎用 endl(时间膨胀一倍多)。
#include <bits/stdc++.h>#define N 1000010using 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/ 最后更新于 2024-11-16,距今已过 469 天
部分内容可能已过时