记录编号	450656	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]寻找道路	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.205 s
提交时间	2017-09-16 17:08:44	内存使用	15.38 MiB

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <queue>
#define maxn 200005
using namespace std;
int n,m,ai,bi,s,t;
struct node{int to,next;}e[maxn*2];
int zz,st[maxn];
void add(int x,int y){
	 e[++zz].to=y;
	 e[zz].next=st[x];
	 st[x]=zz;
}
struct node1{int to,next,id;}ee[maxn*2];
int zz1,st1[maxn];
void adf(int x,int y){
	 ee[++zz1].to=y;
	 ee[zz1].next=st1[x];
	 ee[zz1].id=zz1;
	 st1[x]=zz1;
}
int dfn[maxn],low[maxn],bl[maxn],tim,cnt,sta[maxn],top;
bool vis[maxn],flag[maxn],used[maxn];
int ru[maxn],che[maxn];
void dfs(int x){
	 for(int i=st1[x];i;i=ee[i].next){
	 	 if(used[ee[i].id]) continue;
	 	 int t=ee[i].to;
	 	 che[t]++;
	 	 used[ee[i].id]=1;
	 	 dfs(t);
	 }
}
int dis[maxn];
void spfa(int x){
	 memset(dis,0x3f,sizeof(dis));
     dis[x]=0;
     queue<int> q;
     q.push(x);
     vis[x]=1;
     while(!q.empty()){
     	   int k=q.front();
     	   for(int i=st[k];i;i=e[i].next){
     	   	   int t=e[i].to;
     	   	   if(!flag[t]) continue;
     	   	   if(dis[t]>dis[k]+1){
     	   	   	  dis[t]=dis[k]+1;
     	   	   	  if(!vis[t]){
     	   	   	  	 vis[t]=1;
     	   	   	  	 q.push(t);
     	   	   	  }
     	   	   }
     	   }
     	   q.pop();
     	   vis[k]=0;                    
     }
}
int main(){
	freopen("roadb.in","r",stdin);
	freopen("roadb.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&ai,&bi);
		add(ai,bi);
		adf(bi,ai);
		ru[ai]++;
	}
	scanf("%d%d",&s,&t);
	
	dfs(t);
	for(int i=1;i<=n;i++)
		if(che[i]==ru[i]) flag[i]=1;
	spfa(s);
	if(dis[t]>99999) printf("-1");
	else printf("%d",dis[t]);
}
/*
7 15
2 4
4 6
7 5
5 1
2 3
4 3
6 3
6 2
5 7
2 4
6 7
7 6
2 4
6 7
5 6
7 1
*/