记录编号	442518	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]寻找道路	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.131 s
提交时间	2017-08-27 17:30:02	内存使用	3.56 MiB

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n,m,s,t,head1[10005],h1,head2[10005],h2,vis[10005],book[10005],dis[10005];
struct edge{
	int to,next;
}e1[200005],e2[200005];
void edge_add(int x,int y){
	e1[++h1].to=y;
	e1[h1].next=head1[x];
	head1[x]=h1;
	e2[++h2].to=x;
	e2[h2].next=head2[y];
	head2[y]=h2;
}
void bfs(){
	queue<int>S;
	S.push(t);
	vis[t]=1;
	while(!S.empty()){
		int u=S.front();
		S.pop();
		for(int i=head2[u];i;i=e2[i].next){
			if(!vis[e2[i].to]){
				vis[e2[i].to]=1;
				S.push(e2[i].to);
			}
		}
	}
}
void spfa(){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	book[s]=1;
	queue<int>S;
	S.push(s);
	while(!S.empty()){
		int u=S.front();
		S.pop();
		book[u]=0;
		for(int i=head1[u];i;i=e1[i].next){
			int v=e1[i].to,bo=0;
			for(int j=head1[v];j;j=e1[j].next){
				if(!vis[e1[j].to]){
					bo=1;
					break;
				}
			}
			if(bo)continue;
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				if(!book[v]){
					S.push(v);
					book[v]=1;
				}
			}
		}
	}
	if(dis[t]==dis[0])
	cout<<-1;
	else
	cout<<dis[t];
}
int main()
{
	freopen("roadb.in","r",stdin);
	freopen("roadb.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		edge_add(x,y);
	}
	scanf("%d%d",&s,&t);
	bfs();
	spfa();
	return 0;
}