记录编号	220883	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]寻找道路	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.092 s
提交时间	2016-01-20 18:06:57	内存使用	3.50 MiB

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m,s,e;
const int maxn = 10005,maxm = 200005;
struct edge{
	int to,next;
}lst[maxm],lst2[maxm];
int len = 1;
int first[maxn],first2[maxn];
bool elinked[maxn];
bool illegal[maxn];
int dis[maxn];
void bfs1(){
	queue<int> q;
	elinked[e] = true;
	q.push(e);
	while(!q.empty()){
		int pt = first2[q.front()];
		q.pop();
		for(;pt;pt=lst2[pt].next){
			if(!elinked[lst2[pt].to]){
				elinked[lst2[pt].to] = true;
				q.push(lst2[pt].to);
			}
		}
	}
}
void bfs2(){
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int pt = first[q.front()],tmp = q.front();
		q.pop();
		for(;pt;pt = lst[pt].next){
			if(dis[lst[pt].to]==0&&!illegal[lst[pt].to]){
				dis[lst[pt].to] = dis[tmp]+1;
				q.push(lst[pt].to);
			}
		}
	}
}
int main(){
	freopen("roadb.in","r",stdin);
	freopen("roadb.out","w",stdout);
	scanf("%d %d",&n,&m);
	int a,b;
	for(int i = 0;i<m;++i){
		scanf("%d %d",&a,&b);
		lst[len].to = b;
		lst[len].next = first[a];
		lst2[len].to = a;
		lst2[len].next = first2[b];
		first[a] = first2[b] = len++;
	}
	scanf("%d %d",&s,&e);
	bfs1();
	if(!elinked[s]||first[s]==0)printf("-1\n");
	else{
		for(int i = 1;i<=n;++i){
			for(int pt = first[i];pt;pt = lst[pt].next){
				if(!elinked[lst[pt].to]){
					illegal[i]=true;
					break;
				}
			}
		}
		bfs2();
		if(dis[e]==0)printf("-1\n");
		else printf("%d\n",dis[e]);
	}
	fclose(stdin);fclose(stdout);
}