记录编号	402572	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2015] 雅加达的摩天楼	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.878 s
提交时间	2017-05-06 20:39:12	内存使用	12.41 MiB

#include<cstdio>
#include<queue>
using namespace std;
const int N=1e5+10;
int n,m,S,T,w[N],head[N],next[N],cnt;
int dis[N];bool vis[N];
queue<int> Q[N];
int main()
{
	freopen("skyscraper.in","r",stdin);
	freopen("skyscraper.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=0;i<m;i++){
		int f,t;
		scanf("%d%d",&f,&t);
		if (!i) S=f;
		if (i==1) T=f;
		w[++cnt]=t;
		next[cnt]=head[f];
		head[f]=cnt;
	}
	for (int i=0;i<n;i++) dis[i]=1e9;
	dis[S]=0;Q[0].push(S);
	for (int i=0;i<N;i++)
	while (!Q[i].empty()){
		int v=Q[i].front();Q[i].pop();
		if (vis[v]) continue;
		vis[v]=1;
		for (int i=head[v];i;i=next[i]){
			int len=w[i];
			for (int i=v,D=dis[v];i>=0;i-=len,D++)
				if (dis[i]>D) dis[i]=D,Q[D].push(i);
			for (int i=v,D=dis[v];i<n;i+=len,D++)
				if (dis[i]>D) dis[i]=D,Q[D].push(i);
		}
	}
	printf("%d\n",dis[T]<1e9?dis[T]:-1);
	return 0;
}