思路
这是一道纯纯暴力题,因为我们可以证明它的状态数不会超过 \(n\sqrt n\) 级别:
-
若 \(p \le \sqrt n\) 时,显然状态数不会超过 \(n\sqrt n\)
-
若 \(p > \sqrt n\) 时,它经过的地方数 \(<\sqrt n\),因此状态数不超过 \(m\sqrt n\)
由于 \(n,m\) 同阶,因此总状态数不超 \(n\sqrt n\)
因此我们可以直接构图,跑最短路
又因为这是一个无权图,因此直接 bfs
即可
代码
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define LL long long
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
#define PFOR(i, x) for(int i = he[x]; i; i = r[i].nxt)
inline int rd()
{
int sign = 1, re = 0; char c = getchar();
while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
return sign * re;
}
int n, m, S, T;
std::vector<int> f[30005];
struct Node {int b, p, st; Node(int B, int P, int ST) : b(B), p(P), st(ST) {}};
std::queue<Node> q;
std::bitset<30005> vis[30005];
inline void bfs()
{
for(int i : f[S]) q.push(Node(S, i, 0)), vis[S][i] = 1;
f[S].clear();
while(!q.empty())
{
int b = q.front().b, p = q.front().p, st = q.front().st;
q.pop();
if(b + p == T || b - p == T) {printf("%d", st + 1); exit(0);}
if(b + p <= n)
{
if(!vis[b + p][p]) q.push(Node(b + p, p, st + 1)), vis[b + p][p] = 1;
if(!f[b + p].empty())
{
for(int i : f[b + p]) if(!vis[b + p][i])
q.push(Node(b + p, i, st + 1)), vis[b + p][i] = 1;
f[b + p].clear();
}
}
if(b - p > 0)
{
if(!vis[b - p][p]) q.push(Node(b - p, p, st + 1)), vis[b - p][p] = 1;
if(!f[b - p].empty())
{
for(int i : f[b - p]) if(!vis[b - p][i])
q.push(Node(b - p, i, st + 1)), vis[b - p][i] = 1;
f[b - p].clear();
}
}
}
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
n = rd(), m = rd();
S = rd() + 1, f[S].emplace_back(rd());
T = rd() + 1, f[T].emplace_back(rd());
if(S == T) return puts("0"), 0;
FOR(i, 3, m)
{
int b = rd() + 1;
f[b].emplace_back(rd());
}
bfs();
puts("-1");
return 0;
}
标签:Node,int,摩天楼,P3645,APIO2015,rd,vis,st,include
From: https://www.cnblogs.com/zuytong/p/16715064.html