记录编号	256072	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2015] 雅加达的摩天楼	最终得分	100
用户昵称	zzzzzfy	是否通过	通过
代码语言	C++	运行时间	0.550 s
提交时间	2016-04-29 11:15:51	内存使用	0.88 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];
struct edge{
	int v,next,w;
	edge(){}
	edge(int v,int next,int w):v(v),next(next),w(w){}
};
vector<edge> e;
struct node{
	int x,d;
	node(){}
	node(int x,int d):x(x),d(d){}
};
bool operator <(node a,node b){
	return a.d>b.d;
}
priority_queue<node> q;
vector<int> bl[N];
void add(int u,int v,int w){
//	if(num==N*500) return;
//	cout<<u<<" "<<v<<" "<<w<<endl;
	e.push_back(edge(v,first[u],w));
	first[u]=e.size()-1;
}
void spfa(){
	memset(d,0x3f,sizeof d);
	q.push(node(S,0));d[S]=0;
//	cout<<d[S]<<" "<<d[T]<<endl;
	while(!q.empty()){
		node u=q.top();q.pop();
		if(inq[u.x]) continue;
		inq[u.x]=true;
		for(int i=first[u.x];i;i=e[i].next){
			int v=e[i].v;
			if(d[v]>d[u.x]+e[i].w){
				d[v]=d[u.x]+e[i].w;
				q.push(node(v,d[v]));
			}
		}
	}
}
int main(){
	freopen("skyscraper.in","r",stdin);
	freopen("skyscraper.out","w",stdout);
	scanf("%d%d",&n,&m);
	e.push_back(edge(0,0,0));
	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++){
//			cout<<bl[i][j]<<" ";
			if(bl[i][j]!=bl[i][j-1]) q[++top]=bl[i][j];
		}
//		cout<<endl;
	//	for(int j=1;j<=top;j++) cout<<q[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;
			//	cout<<i<<" "<<x<<endl;
				if(bl[x].size()) add(i,x,num);
			}
			x=i,k=q[j],num=0;
			while(1){
				x+=k;num++;
				if(x>n) break;
			//	cout<<i<<" "<<x<<endl;
				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
*/