记录编号	250892	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]寻找道路	最终得分	100
用户昵称	甘罗	是否通过	通过
代码语言	C++	运行时间	0.091 s
提交时间	2016-04-16 11:47:49	内存使用	0.75 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

int i,j,n,m,x,y,zd,qd,t,w,p;
bool f[10010];
int d[10010],bj[10010],z[20020],b[10010];
vector<int> l[10010];
vector<int> ll[10010];

void bfs(){
	int we,ti,i;    //  we,ti:BFS队列指针
	we=0; ti=0;
	z[++we]=zd;
	ti++;
	bj[zd]=1;
	while (ti<=we) {
		if (ll[z[ti]].size()==0) {
			ti++;
			continue;
		}
		for (i=0;i<=ll[z[ti]].size()-1;i++)
		{
			if (bj[ll[z[ti]][i]]==0) {
			z[++we]=ll[z[ti]][i];
			bj[ll[z[ti]][i]]=1; 
			}
		}
		ti++;
	}      //   广搜处理

	return;
}	//   BFS反向建图求终点能到达的点

void work(){
	int i,bh;
	for (i=1;i<=n;i++)
	{
		if (l[i].size()==0) continue;
		bh=0;
		for (j=0;j<=l[i].size()-1;j++)
		if (bj[l[i][j]]==0) {
			bh=1; break;
		}                //   标记是不是每个点都能到终点 
	if (bh!=1) b[i]=1;
	}
	b[zd]=1;
	return;
}     //   逐个判断每个点是否符合题意

int main(){
	freopen("roadb.in","r",stdin);
	freopen("roadb.out","w",stdout);
	scanf("%d%d",&n,&m);
	
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		if (x==y) continue;
		l[x].push_back(y);
		ll[y].push_back(x);
		}

	scanf("%d %d",&qd,&zd);

	bfs();	work();

	if (b[qd]==0) {
		printf("-1\n"); return 0;
	}
	
	memset(z,0,sizeof(z));
	for (i=1;i<=n;i++)
	d[i]=0x7fffffff-1000;
	d[qd]=0;
	t++;
	z[t]=qd;	f[qd]=true;
	
	while (t!=w) {
		w=(w+1)%n;
		p=z[w];
		f[p]=false;
		if (l[p].size()==0) continue;
		for (i=0;i<=l[p].size()-1;i++)
		if (b[l[p][i]]==1&&d[p]+1<d[l[p][i]]) {
		d[l[p][i]]=d[p]+1;
		if (not f[l[p][i]]) {
			t=(t+1)%n;
			z[t]=l[p][i];	f[l[p][i]]=true;
		}
		}
	}        //   SPFA 
	if (d[zd]==0x7fffffff-1000) printf("-1\n"); else
	printf("%d\n",d[zd]);
	return 0;
}