thinkphp做的网站怎么预览,网站首页导航代码,淮安网站建设公司,山西省网站备案E. Escape 思路#xff1a;
可以看成 Sneaker 和杀戮机器人都不能在原地停留#xff0c;然后杀戮机器人有个活动范围限制。如果 Sneaker 和杀戮机器人可以在原地停留#xff0c;那么 Sneaker 到达一个点肯定会尽可能早#xff0c;而且时间必须比杀戮机器人到达这个点短。那…E. Escape 思路
可以看成 Sneaker 和杀戮机器人都不能在原地停留然后杀戮机器人有个活动范围限制。如果 Sneaker 和杀戮机器人可以在原地停留那么 Sneaker 到达一个点肯定会尽可能早而且时间必须比杀戮机器人到达这个点短。那么预处理一下每个点最早什么时候会被杀戮机器人到达然后在这个基础上处理出1 ∼n 的最短路即可。
由于每个机器每个时刻都不会停。我们需要分奇数和偶数时刻来记录它们会出现的位置。
我们把点拆分为iin两个点做记录。
先预处理bfs记录所有机器人的可达点。
再跑一遍bfs计算从起点到终点需要的最短路径。单组数据时间复杂度 O(n m)。
代码
#include bits/stdc.h
#define int long long
#define pii pairint, 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;
vectorint 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);queueint 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]);vectorint 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;
}
