记录编号	450600	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]寻找道路	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.090 s
提交时间	2017-09-16 16:37:54	内存使用	5.12 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
#define N 20010
using namespace std;
int n,m,s,t;
struct haha{
	int next,to;
}edge[301000],edgefan[301000];
int head[N],headfan[N],cnt=1,cntfan=1;
void add(int u,int v){
	edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;
}
void addfan(int u,int v){
	edgefan[cntfan].to=v;edgefan[cntfan].next=headfan[u];headfan[u]=cntfan++;
}
bool flag[N];
void bfs1(){
	queue<int> q;
	q.push(t);
	flag[t]=1;
	while(!q.empty()){
		int temp=q.front();q.pop();
		for(int i=headfan[temp];i;i=edgefan[i].next){
			int to=edgefan[i].to;
			if(flag[to]==0){
				flag[to]=1;
				q.push(to);
			}
		}
	}
}
struct xixi{
	int now,w;
};
int ans=-1;
bool cun[N],vis[N];
void bfs2(){
	queue<xixi> q;
	q.push((xixi){s,0});
	cun[s]=1;vis[s]=1;
	while(!q.empty()){
		xixi temp=q.front();q.pop();
		int now=temp.now,w=temp.w;
		for(int i=head[now];i;i=edge[i].next){
			int to=edge[i].to;
			if(to==t){
				ans=w+1;return;
			}
			if(cun[to]==1&&vis[to]==0){
				vis[to]=1;
				q.push((xixi){to,w+1});
			}
		}
	}
}
int main(){
	freopen("roadb.in","r",stdin);
	freopen("roadb.out","w",stdout);
	scanf("%d%d",&n,&m);
	pos(i,1,m){
		int x,y;scanf("%d%d",&x,&y);
		if(x==y) continue;
		add(x,y);addfan(y,x);
	}
	scanf("%d%d",&s,&t);
	bfs1();
	
	//system("pause");
	//flag[s]=flag[t]=1;
	pos(x,1,n){
		if(x!=s&&x!=t){
			int u=0;
			for(int i=head[x];i;i=edge[i].next){
				int to=edge[i].to;
				if(flag[to]==0){
					u=1;break;
				}
			}
			if(u==0){
				cun[x]=1;
			}
		}
	}//return 0;
	/*pos(i,1,n){
		cout<<"i="<<i<<"  cun="<<cun[i]<<endl;
	}*/
	bfs2();
	cout<<ans;
	return 0;
}