Description：

有 $n$ 个摩天楼， $m$ 只狗，第 $i$ 只狗在 $b[i]$ ，跳跃距离为 $p[i]$ ，求让 $1$ 号狗把消息传递给 $2$ 号狗的最少跳跃次数。

$1\leqslant n\leqslant 30000$

Solution：

首先发现肯定不会跳回来，那么可以把每只狗向他能跳到的所有位置连相应权值边，但这样连边是 $O(n^2)$ 的，再跑 $dijkstra$ 复杂度 $O(n+m)\log n$ 肯定是不行的， $n\leqslant30000$ 这个复杂度启示我们复杂度可能带一个根号，要想根号分治的话肯定是把跳跃距离分治，大于 $\sqrt n$ 的每只狗最多只会建 $\sqrt n$ 条边，这个可以暴力建，小于 $\sqrt n$ 的边只有 $\sqrt n$ 种可能的取值，考虑把所有的一起建，如果从某个位置一步可以跳到下一个位置，下一个位置也有跳跃距离相同的狗，那么后面那只狗就没用了，也就是说可以对每个 $k<\sqrt n$ 的向后一个建边，但是如果这个位置没有狗跳跃距离为 $k$ ，那就由上一个跳跃距离为 $k$ 的狗的位置向下一个连边，正反各连一次，可以发现这样连边包含了所有可能情况且边的数量为 $O(n\sqrt n)$ ，于是时间复杂度就被压缩成了 $O(n\sqrt n\log n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 30010

int b[MAXN],l[MAXN];

#define BLOCK 170

struct edge

{

	int to,nxt,v;

}e[MAXN * 400];

int lin[MAXN] = {0};

int edgenum = 0;

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

bool tag[MAXN][BLOCK];

int d[MAXN];

bool v[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&b[i],&l[i]);

		++b[i];if(l[i] < BLOCK)tag[b[i]][l[i]] = true;

	}

	for(int i = 1;i <= m;++i)

	{

		if(l[i] >= BLOCK)

		{

			for(int j = 1;b[i] - l[i] * j >= 1;++j)add(b[i],b[i] - l[i] * j,j);

			for(int j = 1;b[i] + l[i] * j <= n;++j)add(b[i],b[i] + l[i] * j,j);

		}

	}

	for(int i = 1;i < BLOCK;++i)

	{

		for(int st = 1;st <= i;++st)

		{

			int lastpos = 0;

			int p;

			for(p = st;p <= n;p += i)

			{

				if(lastpos != 0)add(lastpos,p,(p - lastpos) / i);

				if(tag[p][i])lastpos = p;

			}

			lastpos = 0;

			for(;p >= 1;p -= i)

			{

				if(lastpos != 0)add(lastpos,p,(lastpos - p) / i);

				if(tag[p][i])lastpos = p;

			}

		}

	}

	int s = 1,t = 2;

	memset(v,false,sizeof(v));

	memset(d,0x3f,sizeof(d));

	d[b[s]] = 0;

	priority_queue< pair<int,int> > q;

	q.push(make_pair(0,b[s]));

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(v[k])continue;

		v[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				d[e[i].to] = d[k] + e[i].v;

				q.push(make_pair(-d[e[i].to],e[i].to));

			}

		}

	}

	if(d[b[t]] != 0x3f3f3f3f)cout << d[b[t]] << endl;

	else puts("-1");

	return 0;

}