WA 了 #10
代码如下:
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register
const int B=200;
il int read()
{
int re=0,k=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')k=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){re=re*10+ch-48;ch=getchar();}
return re*k;
}
il void write(int x)
{
if(x<0)return putchar('-'),write(-x),void();
if(x<10)return putchar(x+48),void();
return write(x/10),write(x%10),void();
}
int head[12000005],n,tot,m,b[30005],p[30005],num[205][30005],cnt,dis[12000005];
struct ss{
int node,nxt;
bool w;
}e[20000005];
il void add(int u,int v,int w)
{
e[++tot].nxt=head[u];
e[tot].node=v;
e[tot].w=w;
head[u]=tot;
}
void init()
{
for(rg int i=1;i<=B;i++)
for(rg int j=0;j<n;j++)
{
num[i][j]=++cnt;
if(j>=i)add(num[i][j],num[i][j-i],1),add(num[i][j-i],num[i][j],1);
add(num[i][j],j,0);
}
}
void newadd(int b,int p)
{
if(p>B)
{
for(rg int i=b%p;i<n;i+=p)
{
int u=++cnt;
if(i>=p)
{
add(cnt-1,u,1);
add(u,cnt-1,1);
}
if(i==b)add(b,cnt,0);
add(cnt,i,0);
}
}
else
//for(rg int i=1;i<=B;i++)
add(b,num[p][b],0);
}
deque<int> q;
bool vis[12000005];
signed main()
{
n=read();m=read();
cnt=n-1;
init();
for(rg int i=1;i<=m;i++)
{
b[i]=read();p[i]=read();
newadd(b[i],p[i]);
}
q.push_back(b[1]);dis[b[1]]=0;
while(!q.empty())
{
int t=q.front();q.pop_front();
if(vis[t])continue;
vis[t]=1;
for(rg int i=head[t];i;i=e[i].nxt)
{
int y=e[i].node;
if(vis[y])continue;
dis[y]=dis[t]+e[i].w;
if(e[i].w)
q.push_back(y);
else q.push_front(y);
}
}
if(!vis[b[2]])write(-1);
else write(dis[b[2]]);
}