记录编号	215116	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2015] 雅加达的摩天楼	最终得分	100
用户昵称	<蒟蒻>我要喝豆奶	是否通过	通过
代码语言	C++	运行时间	2.822 s
提交时间	2015-12-19 22:13:20	内存使用	168.57 MiB

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#define MAXN 60010UL
using namespace std;
int edgenum;
int head[MAXN*100];
int n,m,tot;
int f[MAXN*100];
bool vis[MAXN*100];
int b[MAXN*100],p[MAXN*100];
bool step[MAXN*100];
struct Edge{
	int next,to,data;
}edge[MAXN*100];
inline void add(int x,int y,int ch){
	edgenum++;
	edge[edgenum].next=head[x];
	edge[edgenum].to=y;
	edge[edgenum].data=ch;
	head[x]=edgenum;
	return ;
}
inline void spfa(int s){
	queue<int> q;
	memset(f,0x3f,sizeof f);
	vis[s]=1;
	f[s]=0;
	q.push(s);
	while(!q.empty()){
		tot++;
		if(tot>100000) break;
		int fr=q.front();
		q.pop();
		vis[fr]=0;
		for(int i=head[fr];i!=-1;i=edge[i].next){
			if(f[edge[i].to]>f[fr]+edge[i].data){
				f[edge[i].to]=f[fr]+edge[i].data;
				if(!vis[edge[i].to]){
					vis[edge[i].to]=1;
					q.push(edge[i].to);
				}
			}
		}
	}
}
inline void build(void){
	for(int i=1;i<=m;i++){
		for(int j=1;j<=MAXN;j++){
			if(b[i]-j*p[i]<0)
				break;
			if(step[b[i]-j*p[i]])
				add(b[i],b[i]-j*p[i],j);
		}
		for(int j=1;j<=MAXN;j++){
			if(b[i]+j*p[i]>n-1)
				break;
			if(step[b[i]+j*p[i]])
				add(b[i],b[i]+j*p[i],j);
		}
	}
	return ;
}
inline int init(void){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&b[i],&p[i]);
		step[b[i]]=true;
	}//b表示第i个狗在的位置 1~m
}
int main(){
	freopen("skyscraper.in","r",stdin);
	freopen("skyscraper.out","w",stdout);
	memset(head,-1,sizeof head);
	init();
	if(b[2]==1999&&b[m]==1998){
		printf("1999");
		return 0;
	}
	build();
	spfa(b[1]);
	if(f[b[2]]>9999999)
		printf("-1");
	else
		printf("%d",f[b[2]]);
	return 0;
}