Description

印尼首都雅加达市有 $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≤b−p<N$）或 $b+p$ （如果 $0≤b+p<N$）的摩天楼。

编号为 $0$ 的 doge 是所有 doge 的首领，它有一条紧急的消息要尽快传送给编 号为 $1$ 的 doge。任何一个收到消息的 doge 有以下两个选择:

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

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

Solution

这道题建图非常妙，一道最短路题建图甚至比网络流还要精妙。

考虑暴力建图，对每个点 $i$ 都向其能到达的点 $j$ 连边，很显然最坏情况需要 $n^2$ 条边，会炸。

考虑换一种建边方式，对于每次能跳 $x$ 步的点 $i$，连接 “…、$(i,i-x)$、$(i,i+x)$、$(i+x,i+2x)$、$(i+2x,i+3x)$、… ” 这些边。

但是这个做法是错的，因为当你到达一个点的时候，你可能不是经由上一只可以跳 $x$ 步的 doge 过来的，这个点上的 doge 也不能跳 $x$ 步，所以再走 $x$ 步的这条边就错了。

解决办法是建虚点，对于每个点建立一层虚点，虚点之间用 $x$ 长度的边连接，每一层虚点相互独立。对应的主点向其连接长度为 $0$ 的单向边，每个虚点向每个同位置的主点连接长度为 $0$ 的单向边，这样，就确保了每只 doge 互不干扰。

更进一步，虚点是可以重复利用的。一排虚点上，每个虚点都向左右离它 $x$ 个长度的点建边，这排虚点就可以给所有长度为 $x$ 的 doge 用，而不会冲突（在 $i$ 点只能跳到 $i+x$ 和 $i-x$ 两个点）。

所以我们可以为每个跳跃长度的 doge 都建立一排虚点，像这样：

但是这样做有一个问题，如果 $n$ 大了点数还是要过多。

我们可以设定一个阈值 $k$，小于 $k$ 的就走虚边，大于 $k$ 的就直接在原来的点上连接所有能到达的点。所以我们只需要建 $k$ 层虚点，时间复杂度足够。

k 如何取值？一般来说我们喜欢令 $k=\sqrt n$，但在这道题里却不是最优的，所以这道题有 $k=min\{100,\sqrt n\}$ 这种操作（$k$ 过大层数多反而没有直接暴力建边快）。

实际上，$k$ 的最佳取值是 $\sqrt {\frac13n}$，因为我太菜不会证，这里放一个洛谷题解的证明：

这是样例的最终建图：

用 SPFA (Dijkstra 会 T) 跑一遍最短路即可。

注意有个坑，是 $0$ 号 $doge$ 到 $1$ 号 $doge$，而不是 $0$ 号楼到 $1$ 号楼。

应该是最近写的最走心的博文了。

Code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
int n,m;
int head[3100000],top=0,d[3100000];
bool v[3100000]; 
struct node{
    int v,w,next;
}s[18000005];
void add(int a,int b,int c){
    s[top].v=b;
    s[top].w=c;
    s[top].next=head[a];
    head[a]=top++;
}
void spfa(int x,int maxn){
    queue<int> q;
    for(int i=0;i<=maxn;i++){
        d[i]=214748364;
        v[i]=false;
    }
    d[x]=0;
    q.push(x);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        v[now]=false;
        for(int i=head[now];i!=-1;i=s[i].next){
            int to=s[i].v;             
            if(d[to]==214748364||d[to]>d[now]+s[i].w){
                d[to]=d[now]+s[i].w;
                if(!v[to]){
                    v[to]=true;
                    q.push(to);
                }
            }
        }
    }
}
int main(){
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    int siz=min(int(sqrt(n)),100);
    for (int i=1;i<=siz;i++){
    	for (int j=0;j<=n-1;j++){
    		if (i+j>=n){
    			break;
			}
    		add(i*n+j,i*n+j+i,1);
    		add(i*n+j+i,i*n+j,1);
		}
    	for (int j=0;j<=n-1;j++){
    		add(i*n+j,j,0);
		}
	}
    int S,T;
    for (int i=1;i<=m;i++){
    	int x=read(),y=read();
    	if (i==1){
    		S=x;
		}
		if (i==2){
			T=x;
		}
    	if (y>siz){
    		for (int j=x-y,k=1;j>=1;j-=y,k++){
    			add(x,j,k);
			}
			for (int j=x+y,k=1;j<=n-1;j+=y,k++){
				add(x,j,k);
			}
		}else{
			add(x,y*n+x,0);
		}
	}
	spfa(S,(siz+1)*n);
	if (d[T]>=214748364){
		d[T]=-1;
	}
    cout<<d[T];
    return 0;
}