2024icpc(Ⅱ)网络赛补题E

E. Escape

思路：

可以看成 Sneaker 和杀戮机器人都不能在原地停留，然后杀戮机器人有个活动范围限制。如果 Sneaker 和杀戮机器人可以在原地停留，那么 Sneaker 到达一个点肯定会尽可能早，而且时间必须比杀戮机器人到达这个点短。那么预处理一下每个点最早什么时候会被杀戮机器人到达，然后在这个基础上处理出1 ∼n 的最短路即可。

由于每个机器每个时刻都不会停。我们需要分奇数和偶数时刻，来记录它们会出现的位置。

我们把点拆分为i，i+n两个点做记录。

先预处理bfs，记录所有机器人的可达点。

再跑一遍bfs，计算从起点到终点，需要的最短路径。单组数据时间复杂度 O(n + m)。

代码：

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 5;
const int mod = 998244353;
#define ll long long
const int maxn = 1000010;
#define inf 2000000000int n, m, d;
vector<int> g[maxn];
int k;
int dis[maxn];
int pre[maxn];
int dis2[maxn];
int u, v;
bool vis[maxn];void solve()
{scanf("%lld%lld%lld", &n, &m, &d);// initfor (int i = 0; i <= n; ++i){g[i].clear();vis[i] = vis[i + n] = 0;pre[i] = pre[i + n] = 0;dis[i] = dis[i + n] = inf;dis2[i] = dis2[i + n] = inf;}// build graghfor (int i = 1; i <= m; ++i){scanf("%lld%lld", &u, &v);--u, --v; // 点下标偏移到[0,n-1]g[u].push_back(v);g[v].push_back(u);}// cal dis2.scanf("%lld", &k);queue<int> q;for (int i = 1; i <= k; ++i){scanf("%lld", &u);--u; // 点下标偏移到[0,n-1]q.push(u);vis[u] = 1;dis2[u] = 0;}while (!q.empty()){u = q.front();q.pop();int f = u / n; // 偶数/奇数时刻int x = u % n; // 原始点if (dis2[u] == d){ // 超出范围continue;}for (auto v : g[x]){int y = v + n * (!f); // 下一个点if (!vis[y] && dis2[y] > dis2[u] + 1){dis2[y] = dis2[u] + 1;q.push(y);vis[y] = 1;}}}// cal dis.for (int i = 0; i <= 2 * n; ++i){vis[i] = 0;}pre[0] = -1; // 记录位置，便于输出答案dis[0] = 0;q.push(0);vis[0] = 1;while (!q.empty()){ // bfs过程同上，不赘述u = q.front();q.pop();int f = u / n;int x = u % n;for (auto v : g[x]){int y = v + n * (!f);if (dis[y] <= dis[u] + 1){continue;}if (dis[u] + 1 >= dis2[y]){continue;}dis[y] = dis[u] + 1;pre[y] = u;q.push(y);vis[y] = 1;}}if (!vis[n - 1] && !vis[2 * n - 1]){ //printf("-1\n");return;}int ed = dis[n - 1] < dis[2 * n - 1] ? n - 1 : 2 * n - 1;printf("%lld\n", dis[ed]);vector<int> res;while (ed != -1){res.push_back(ed);ed = pre[ed];}reverse(res.begin(), res.end());for (auto x : res){// 这里 x % n 求出原始点，// +1是为了复位，偏移到 [1,n]printf("%lld ", x % n + 1);}printf("\n");
}signed main()
{// std::ios::sync_with_stdio(0);// cin.tie(0);// cout.tie(0);int t = 1;scanf("%lld", &t);while (t--){solve();}return 0;
}