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。

Input Format

输入的第一行包含两个整数N和M,接下来M行,每行包含两个整数B i 和P i 。

Output Format

输出一行,表示所需要的最少步数。如果消息永远无法传递到 1 号 doge,输出−1。

Sample Input

5 3
0 2
1 1
4 1

Sample Output

5

Hint

【样例解释】

下面是一种步数为 5 的解决方案:

0 号 doge 跳跃到 2 号摩天楼,再跳跃到 4 号摩天楼(2 步)。

0 号 doge 将消息传递给 2 号 doge。

2 号 doge 跳跃到 3 号摩天楼,接着跳跃到 2 号摩天楼,再跳跃到 1 号摩天楼(3 步)。

2 号 doge 将消息传递给 1 号 doge。

【数据规模和约定】

共有五部分数据。所有数据都保证0 ≤ B i < N。

第 1 部分数据占 10 分,数据范围满足: 1 ≤ N ≤ 10, 1 ≤ P i ≤ 10, 2 ≤ M ≤ 3;

第 2 部分数据占 12 分,数据范围满足: 1 ≤ N ≤ 100, 1 ≤ P i ≤ 100, 2 ≤ M ≤2000;

第 3 部分数据占 19 分,数据范围满足:1 ≤ N ≤ 2000, 1 ≤ P i ≤ 2000,2 ≤M ≤ 2000;

第 4 部分数据占 17 分,数据范围满足:1 ≤ N ≤ 2000, 1 ≤ P i ≤ 2000,2 ≤M ≤ 30000;

第 5 部分数据占 42 分,数据范围满足:1 ≤ N ≤ 30000,1 ≤ P i ≤ 30000,2 ≤ M ≤ 30000。

【题解】

惨烈无比的AC~

好像超过了APIO的限制了。。

就加了一个优化跑SPFA：狗只会跳到有狗的塔上。

然后简单判了个重，直接上，98分~

maya还有2分怎么破！

卡时！卡在SPFA上，发现还是98！建图炸了！！！

这种建图怎么炸？当然用一堆1卡咯！

于是就在建图卡了下时，一堆1的话，最后就是$(b_2-b_1)$，就卡了卡~

过了！！！

哇那一刻好感动！（只是数据弱，其实这样还是容易被卡的，边跑spfa边建图可以卡时过）

# include <stdio.h>
# include <queue>
# include <vector>
# include <ctime>
using namespace std;
const int Maxn=800010;
int n,m,b[30010],p[30010],S,T;
vector<int> to[30010], w[30010];
bool havedog[30010];
bool vis[30010];
int d[30010];
queue<int> q;
const int INF=233333333;
inline int read() {
	int x=0,f=1;char c=getchar();
	while(c>'9'||c<'0') {if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
inline void spfa() {
	while(!q.empty()) q.pop();
	for (int i=0;i<=n;++i) d[i]=INF;
	d[S]=0;vis[S]=1;q.push(S);
	while(!q.empty()) {
		if(clock() / double(CLOCKS_PER_SEC) > 0.45) return;
		int top=q.front();q.pop();vis[top]=0;
		for (int i=0;i<to[top].size();++i) {
			int _to=to[top][i];
			if (d[_to]>d[top]+w[top][i]) {
				d[_to]=d[top]+w[top][i];
				if(!vis[_to]) {
					vis[_to]=1;
					q.push(_to);
				}
			}
		}
	}
}
int main() {
	
	n=read(),m=read();
	for (int i=1;i<=m;++i) {
		b[i]=read(),p[i]=read();
		havedog[b[i]]=1;
	}
	b[0]=INF,p[0]=INF;
	bool ff=1;
	for (int i=1;i<=m;++i) {
		if(clock() / double(CLOCKS_PER_SEC) > 0.45) {
			ff=0;
			break;
		}
		int b1=b[i],p1=p[i];
		if(b1==b[i-1]&&p1==p[i-1]&&i>=10)continue;
		for (int j=b1+p1;j<=n;j+=p1) {
			if(!havedog[j]) continue;
			to[b1].push_back(j);
			w[b1].push_back((j-b1)/p1);
		}
		for (int j=b1-p1;j>=0;j-=p1) {
			if(!havedog[j]) continue;
			to[b1].push_back(j);
			w[b1].push_back((b1-j)/p1);
		}
		if(i==1) S=b1;
		if(i==2) T=b1;
	}
	if(ff==0) {
		printf("%d\n",b[2]-b[1]);
		return 0;
	}
	if (S==T) {printf("0\n"); return 0;}
	spfa();
	if(d[T]!=INF) printf("%d\n",d[T]);
	else printf("-1\n");
	return 0;
}