根号分治,跳跃能力小于等于 \(\sqrt N\) 的 doge 不同跳跃能力数量有限,大于 \(\sqrt N\) 的 doge 能跳到的位置有限。
所以状态只有 \(O((N+M)\sqrt N)\) 种,可以接受,用 bitset
判断是否出现比较方便。
然后有一种神奇的东西叫 01BFS,能 \(O(V+E)\) 解决边权仅为 \(0\) 和 \(1\) 的最短路问题。
当选择一条权值为 \(0\) 的边时,塞入队首;当选择一条权值为 \(0\) 的边时,塞入队尾。这样能时刻维护队列的单调性。
值得注意的是,因为本题的特殊性,同一座摩天楼会在不同的跳跃能力下多次入队。但传递消息是不需要花跳跃次数的,所以在一个点拓展完后,就不需要再次拓展了,否则枚举出边的复杂度会退化为 \(O(VE)\)。
还有一个极易忽略的点(建议去 UOJ 上交一发),01BFS 要在出队时打标记而不是入队时,因为有可能第一次是塞入队尾,后面塞入队首可能跳跃次数更少。这样时间复杂度并不会改变,因为仅仅是在 \(O(E)\) 的前提下多塞入了一些点,这些点不会进行拓展。
code:
#include<bits/stdc++.h>
using namespace std;
#define N 30005
#define For(i,x,y)for(i=x;i<=(y);i++)
bitset<N>k[N];
deque<int>tim;
vector<int>vec[N];
deque<pair<int,int> >deq;
int main()
{
pair<int,int>pa;
int n,m,i,b,p,tmp;
scanf("%d%d",&n,&m);
For(i,0,m-1)
{
scanf("%d%d",&b,&p);
vec[b].push_back(p);
if(!i)deq.push_back(make_pair(b,p));
if(i==1)pa=make_pair(b,p);
}
tim.push_back(0);
while(!deq.empty())
{
b=deq.front().first;
p=deq.front().second;
tmp=tim.front();
if(make_pair(b,p)==pa)break;
deq.pop_front();
tim.pop_front();
if(k[b][p])continue;
k[b][p]=1;
if(b>=p)deq.push_back(make_pair(b-p,p)),tim.push_back(tmp+1);
if(b+p<n)deq.push_back(make_pair(b+p,p)),tim.push_back(tmp+1);
while(!vec[b].empty())
{
if(!k[b][vec[b].back()])deq.push_front(make_pair(b,vec[b].back())),tim.push_front(tmp);
vec[b].pop_back();
}
}
printf("%d",(deq.empty()?-1:tmp));
return 0;
}