题目

题目链接：https://www.luogu.com.cn/problem/P3645
印尼首都雅加达市有 \(N\) 座摩天楼，它们排列成一条直线，我们从左到右依次将它们编号为 \(0\) 到 \(N − 1\)。除了这 \(N\) 座摩天楼外，雅加达市没有其他摩天楼。
有 \(M\) 只叫做 doge 的神秘生物在雅加达市居住，它们的编号依次是 \(0\) 到 \(M − 1\)。编号为 \(i\) 的 doge 最初居住于编号为 \(B_i\) 的摩天楼。每只 doge 都有一种神秘的力量，使它们能够在摩天楼之间跳跃，编号为 \(i\) 的 doge 的跳跃能力为 \(P_i\) （\(P_i>0\)）。
在一次跳跃中，位于摩天楼 \(b\) 而跳跃能力为 \(p\) 的 doge 可以跳跃到编号为 \(b − p\) （如果 \(0 \leq b − p<N\)）或 \(b + p\) （如果 \(0 \leq b + p< N\)）的摩天楼。
编号为 \(0\) 的 doge 是所有 doge 的首领，它有一条紧急的消息要尽快传送给编号为 \(1\) 的 doge。任何一个收到消息的 doge 有以下两个选择:

• 跳跃到其他摩天楼上；
• 将消息传递给它当前所在的摩天楼上的其他 doge。

请帮助 doge 们计算将消息从 \(0\) 号 doge 传递到 \(1\) 号 doge 所需要的最少总跳跃步数，或者告诉它们消息永远不可能传递到 \(1\) 号 doge。
\(n,m\leq 30000\)。

思路

记 \(f[x][y]\) 表示到达点 \(x\)，弹跳能力为 \(y\) 的最小步数。

• 若 \(y\leq \sqrt{n}\)，那么 \(f[x][y]\) 的状态数为 \(O(n\sqrt n)\)。
• 若 \(y>\sqrt{n}\)，那么每一只 doge 最多能有 \(\frac{n}{\sqrt{n}}\) 个落脚点，\(f[x][y]\) 的有效状态数为 \(O(m\sqrt{n})\)。

所以直接跑 BFS 就行了。状态判重可以用 bitset。
时间复杂度 \(O((n+m)\sqrt n)\)。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=30010;
int n,m,S,T;
bool vis1[N];
bitset<N> vis[N];
vector<int> id[N];

struct node
{
	int x,y,d;
};
queue<node> q;

void insert(int x,int dis)
{
	vis1[x]=1;
	for (int i=0;i<(int)id[x].size();i++)
		if (!vis[x][id[x][i]])
		{
			q.push((node){x,id[x][i],dis});
			vis[x][id[x][i]]=1;
		}
}

bool bfs()
{
	insert(S,0);
	while (q.size())
	{
		node u=q.front(); q.pop();
		int x=u.x,y=u.y,dis=u.d;
		if (x==T) { cout<<dis; return 1; }
		if (x+y<=n && !vis[x+y][y])
		{
			vis[x][y]=1;
			q.push((node){x+y,y,dis+1});
			if (!vis1[x+y]) insert(x+y,dis+1);
		}
		if (x-y>=1 && !vis[x-y][y])
		{
			vis[x][y]=1;
			q.push((node){x-y,y,dis+1});
			if (!vis1[x-y]) insert(x-y,dis+1);
		}
	}
	return 0;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		id[x+1].push_back(y);
		if (i==1) S=x+1;
		if (i==2) T=x+1;
	}
	if (!bfs()) cout<<"-1";
	return 0;
}