题目地址：P11280
题目难度：普及/提高-
Terry 和 Jom 在一个 个点 条边的有“根”无向连通图上博弈（图的根为
），遵循以下规则：
- Terry 先手；
- 两人轮流在图上移动，每次只能走一条边（也可以睡觉，啥都不干）；
- Terry 不能走到 Jom 所在的结点（我们认为只有 Terry
自投罗网时才会被抓到，即如果 Terry 先移动到结点 后 Jom 在同一回合也移动到 是合法的）。
每次询问给定 Terry 和 Jom 的起点 ，你需要回答 Terry 能否到达点 。
为了避免题面命名给个人理解带来的混乱，本题解将用“猫”（Jom）、“鼠”（Terry）来区分二者。
我们的目的是让鼠无论如何都能在猫之前到达 ，因此我们先考虑猫的最优策略——当猫使用最优策略都无法抓到鼠时，那必定有鼠必胜。
鼠的唯一目的地是 ，因此猫只需先到
点，然后等着它就好了。于是猫一定会沿着到根的最短路径前行，而鼠为了不被抓住也会沿着距离根最短的那条路径行进。我们只需在最开始预处理出每个节点到
的最短距离即可。预估时间复杂度是
的 。
注意不要把 Terry 和 Jom
搞混了；输出量较大，慎用 endl（时间膨胀一倍多）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #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;
}
|
