[题解] ICPC网络预选赛 2024 第二场 E Escape （含题目翻译）
tag: 图论、BFS、最短路
题干为原文DeepL翻译
题目描述
Sneaker 在一个巨大的迷宫中醒来，现在他想逃离这个迷宫。
通过迷宫中每个房间的地图，Sneaker 了解了迷宫的结构。迷宫由 n n n 个房间组成，Sneaker 从 1 1 1 房间开始，出口在 n n n 房间。此外，迷宫中有 m m m 个双向通道，每个通道连接两个不同的房间，且每个通道的两个方向相互隔离。
保证没有两条不同的通道连接同一对房间，也没有通道连接一个房间和它自己。
此外，可以保证任何两个房间都可以通过一系列通道相互到达。
Sneaker 还发现迷宫中有 k k k 个杀手机器人。 i i i 个杀手机器人最初停留在 s i s_i si 房间。显然，Sneaker 不想也不能遇到这些杀手机器人。
如果 Sneaker 开始移动，每个杀手机器人都会同时移动。具体来说，Sneaker 会选择一条与当前房间相连的通道，然后移动到通道另一侧的房间。与此同时，每个杀手机器人也会随机选择一条与其所在房间相连的通道，并移动到通道另一侧的房间。每个杀手机器人将与 Sneaker 同时进出通道。
所有杀手机器人都将记录它们经过的通道。如果一个杀手机器人经过的通道与上一次记录的通道相同，它可以选择从记录中删除这两次出现的通道。换句话说，杀手机器人可以选择撤销记录。
例如，如果杀手机器人目前的记录是 ( 1 , 2 ) , ( 2 , 7 ) , ( 7 , 3 ) (1,2), (2,7), (7,3) (1,2),(2,7),(7,3) ，现在在 3 3 3 房间，它可以选择通过一个新的通道，比如 ( 3 , 6 ) (3,6) (3,6) ，那么它的记录就会变成 ( 1 , 2 ) , ( 2 , 7 ) , ( 7 , 3 ) , ( 3 , 6 ) (1,2), (2,7), (7,3), (3,6) (1,2),(2,7),(7,3),(3,6) ，机器人最终会进入 6 6 6 房间。或者，它也可以穿过 ( 3 , 7 ) (3,7) (3,7) 通道，返回 7 7 7 房间，这样它的记录就会变成 ( 1 , 2 ) , ( 2 , 7 ) (1,2), (2,7) (1,2),(2,7) 。
此外，如果杀手机器人选择通过通道返回 2 2 2 房间，它的记录将变为 ( 1 , 2 ) (1,2) (1,2) 。但是，如果它从 3 3 3 房间直接移动到 2 2 2 房间，它的记录就不会变成 ( 1 , 2 ) (1,2) (1,2) ，而是会变成 ( 1 , 2 ) , ( 2 , 7 ) , ( 7 , 3 ) , ( 3 , 2 ) (1,2), (2,7), (7,3), (3,2) (1,2),(2,7),(7,3),(3,2) 。
此外，所有杀手机器人都有一个相同的自毁参数 d d d 。如果一个杀手机器人到达一个房间，发现它的通行记录超过了 d d d ，它将立即自毁。如果 Sneaker 进入一个房间，发现一个杀手机器人正在自毁或已经自毁，则不视为与该机器人相遇。
现在，Sneaker 想要规划一条最少通道的路线，并确保不会遇到任何杀手机器人。你能帮助他吗？
注意：如果Sneaker从房间 x x x 通过一个通道移动到房间 y y y ，而一个杀手机器人从房间 y y y 通过相同的通道向相反的方向移动到房间 x x x ，那么Sneaker不会遇到杀手机器人，因为通道的两个方向是相互隔离的。Sneaker 只知道每个杀手机器人的初始位置，但不知道它们每时每刻的位置。如果杀手机器人和 Sneaker 同时到达 n n n 房间，那么 Sneaker 就会被认为遇到了杀手机器人，无法从迷宫中逃脱。
输入数据
第一行包含一个整数 T T T 。 ( 1 ≤ T ≤ 1 0 5 ) (1 \leq T \leq 10^5) (1≤T≤105) 表示测试用例的数量。
对于每个测试用例，第一行包含三个整数 n n n 、 m m m 和 d d d ( 2 ≤ n ≤ 2 × 1 0 5 (2 \leq n \leq 2 \times 10^5 (2≤n≤2×105 、 n − 1 ≤ m ≤ min { 5 × 1 0 5 , n ( n − 1 ) 2 } n-1 \leq m \leq \min\{5 \times 10^5, \frac{n(n-1)}{2}\} n−1≤m≤min{5×105,2n(n−1)} 、 $ (1 \leq d < n)$ ，分别代表迷宫的房间数、通道数和自毁参数。
接下来的 m m m 行分别包含两个整数 x i x_i xi 和 y i y_i yi 。 ( 1 ≤ x i < y i ≤ n ) (1 \leq x_i < y_i \leq n) (1≤xi<yi≤n) ，表明第 i i i 条通道连接着 x i x_i xi 房间和 y i y_i yi 房间。
可以保证对于任意 i ≠ j i \neq j i=j 、 x i ≠ x j x_i \neq x_j xi=xj 或 y i ≠ y j y_i \neq y_j yi=yj 。
可以保证任意两个房间可以通过一系列通道相互到达。
第 ( m + 2 ) (m + 2) (m+2) 行包含几个整数。第一个整数 k k k ( 0 ≤ k ≤ n − 2 ) (0\leq k\leq n-2) (0≤k≤n−2) 代表杀手机器人的数量，接下来是 k k k 个整数 s 1 , s 2 , … , s k s_1, s_2, \dots, s_k s1,s2,…,sk 。 ( 2 ≤ s < n ) (2\leq s < n) (2≤s<n) 表示每个杀手机器人所在的初始房间。
保证所有测试用例的 n n n 之和不超过 5 × 1 0 5 5 \times 10^5 5×105 ，所有测试用例的 m m m 之和不超过 2 × 1 0 6 2 \times 10^6 2×106 。
输出数据
对于每个测试用例，如果存在有效路由，则在第一行输出一个整数 p p p ，代表有效路由中的最少通道数。
在第二行中，输出 p + 1 p+1 p+1 个整数 z 0 = 1 , z 1 , … , z p = n z_0=1, z_1, \dots, z_p=n z0=1,z1,…,zp=n ，代表路线经过的房间序列。
如果不存在有效路线，则输出一个整数 − 1 -1 −1 。
测试用例
输入
2
7 8 2
1 2
2 3
3 7
2 5
5 6
3 6
1 4
4 5
1 4
7 8 2
1 2
2 3
3 7
2 5
5 6
3 6
1 4
4 5
1 5
输出
3
1 2 3 7
-1
题解
题目是两定点间的最短路问题，考虑广度优先搜索。问题在于如何避免与机器人相遇，即如何筛选出一条路径，使得走到其中的每一个节点时都一定没有机器人走到同一个点。自然地，我们想到给机器人能走到的点打上标记，在 BFS 的时候避免走到这些点就可以了。于是我们想到，可以在为 Sneaker 进行 BFS 的同时为机器人也进行 BFS ，为机器人走到的点打上标记即可。具体来说，我们要在 Sneaker 扩展每一层之前，为机器人扩展一层。
那么新的问题来了：机器人走到过一个点，并不意味着之后的每一个时刻它都有可能在这个点。例如对于样例来说，机器人第一步能够走到5，但走完第二步不可能在5。进一步我们发现，对于机器人能走到的每一个点来说，如果它在第奇数步走到这个点，那么之后的每一个奇数步都可以走到这个点（因为可以原路返回再回来，步数为2不改变奇偶性，也不会影响自毁的计数），偶数亦然。因此我们将机器人的标记分成奇偶两层，在为 Sneaker 进行 BFS 的时候分奇偶判断一下有没有机器人可能在目标点即可。
问题似乎解决了，但我们似乎忽略了一种特殊情况：图中存在长度为奇数的环。在这种情况下，有可能出现我们第一次无法到达一个点，但经过环改变步数的奇偶性之后可以先于机器人到达这个点。所以我们也要为 Sneaker 在 BFS 标记时区分奇偶性，即可避免此问题。
最后注意到题目需要输出路径，在这里采用了根据节点遍历的时间戳逆序 DFS 的笨方法。
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define int long long
using namespace std;
const int MAXN = 2e5 + 3;
const int MAXM = 1e6 + 3;
// 快读
int read() {
int s = 0, f = 0; char ch = getchar();
while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
// 建图
int first[MAXN], v[MAXM], nt[MAXM];
int te;
inline void addEdge(int x, int y) {
nt[++te] = first[x];
first[x] = te;
v[te] = y;
}
// BFS 用的结构体
struct Point {
int x;
int step;
};
// 回溯路径的DFS
bool flag;
// S的奇偶标记
int vji[MAXN], vou[MAXN];
void dfs(int x, bool ji, int step) {
if (x == 1 && step == 0) {
printf("%lld ", x);
flag = true;
return;
}
for (int eo = first[x]; eo; eo = nt[eo]) {
const int ep = v[eo];
if (ji) {
if (vou[ep] == vji[x] - 1) dfs(ep, !ji, step - 1);
} else {
if (vji[ep] == vou[x] - 1) dfs(ep, !ji, step - 1);
}
if (flag) {
printf("%lld ", x);
return;
}
}
}
// 机器人的奇偶标记
bool ji[MAXN], ou[MAXN];
signed main() {
int t = read();
while (t--) {
// 数据读入与初始化
flag = false;
int n = read(), m = read(), d = read();
for (int i = 1; i <= n; i++) {
first[i] = 0;
vji[i] = vou[i] = 0;
ji[i] = ou[i] = false;
}
te = 0;
for (int i = 1; i <= m; i++) {
int x = read(), y = read();
addEdge(x, y);
addEdge(y, x);
}
// qs存放S的位置，qr存放机器人的位置。因为机器人之间没有区别，放在一个队列里就行
queue <Point> qs, qr;
qs.push((Point){1, 0});
int k;
cin >> k;
for (int i = 1; i <= k; i++) {
int x = read();
qr.push((Point){x, 0});
ou[x] = true;
}
vou[1] = 1;
int ans = -1;
// BFS
while (!qs.empty()) {
const Point p = qs.front();
if (p.x == n) {
ans = p.step;
break;
}
qs.pop();
// 为机器人分奇偶BFS
while (!qr.empty()) {
const Point r = qr.front();
if (r.step > p.step) break;
qr.pop();
if (r.step == d) continue;
for (int eo = first[r.x]; eo; eo = nt[eo]) {
const int ep = v[eo];
if (r.step % 2) { // 当前是奇数步
if (ou[ep]) continue;
qr.push((Point){ep, r.step + 1});
ou[ep] = true;
} else {
if (ji[ep]) continue;
qr.push((Point){ep, r.step + 1});
ji[ep] = true;
}
}
}
// 为S分奇偶BFS
for (int eo = first[p.x]; eo; eo = nt[eo]) {
const int ep = v[eo];
if (p.step % 2) { // 当前是奇数步
if (ou[ep] || vou[ep]) continue;
} else {
if (ji[ep] || vji[ep]) continue;
}
qs.push((Point){ep, p.step + 1});
if (p.step % 2) {
vou[ep] = vji[p.x] + 1;
} else {
vji[ep] = vou[p.x] + 1;
}
}
}
// 输出答案
if (ans == -1) puts("-1");
else {
printf("%lld\n", ans);
dfs(n, ans % 2, ans);
printf("\n");
}
}
return 0;
}
/*
特殊情况：
7 7 1
1 2
1 3
2 3
1 4
4 5
4 6
5 7
1 6
*/