记录编号	256011	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	1983.[APIO 2015] 雅加达的摩天楼	最终得分	100
用户昵称	zzzzzfy	是否通过	通过
代码语言	C++	运行时间	0.323 s
提交时间	2016-04-29 09:20:43	内存使用	169.69 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#define LL long long
using namespace std;
const int N=30100;
int d[N],S,T,first[N],num,n,m;
bool inq[N];
queue<int> q;
struct edge{
	int v,next,w;
}e[N*500];
vector<int> bl[N];
void add(int u,int v,int w){
	e[++num].next=first[u];first[u]=num;
	e[num].v=v;e[num].w=w;
}
void spfa(){
	memset(d,0x3f,sizeof d);
	q.push(S);d[S]=0;
//	cout<<d[S]<<" "<<d[T]<<endl;
	while(!q.empty()){
		int u=q.front();q.pop();inq[u]=false;
		for(int i=first[u];i;i=e[i].next){
			int v=e[i].v;
			if(d[v]>d[u]+e[i].w){
				d[v]=d[u]+e[i].w;
				if(!inq[v]){
					inq[v]=true;
					q.push(v);
				}
			}
		}
	}
}
int main(){
	freopen("skyscraper.in","r",stdin);
	freopen("skyscraper.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		x++;
		if(i==1) S=x;if(i==2) T=x;
	//	cout<<x<<"! "<<y<<endl;
		bl[x].push_back(y);
	}
//	cout<<bl[5].size()<<"lasjf"<<endl;
	for(int i=1;i<=n;i++){
		if(!bl[i].size()) continue;
	//	cout<<i<<" "<<bl[i].size()<<"!"<<endl;
		sort(bl[i].begin(),bl[i].end());
		int q[31000];
		int top=0;q[++top]=bl[i][0];
		for(int j=1;j<bl[i].size();j++){
			if(bl[i][j]!=bl[i][j-1]) q[++top]=bl[i][j];
		}
		for(int j=1;j<=top;j++){
			int x=i,k=q[j],num=0;
			while(1){
				x-=k;num++;
				if(x<=0) break;
				if(bl[x].size()) add(i,x,num);
			}
			x=i,k=q[j],num=0;
			while(1){
				x+=k;num++;
				if(x>n) break;
				if(bl[x].size()) add(i,x,num);
			}
		//	if(q[j]==1) break;
		}
	}
	spfa();
	if(d[T]==d[0]) cout<<"-1"<<endl;
	else cout<<d[T]<<endl;
	return 0;
}
/*
7 3
3 9
5 8
0 8
*/