记录编号	333616	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]寻找道路	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.125 s
提交时间	2016-10-31 07:38:47	内存使用	3.46 MiB

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 10000 + 10 ;
const int maxm = 200000 + 10;

int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

struct Edge{
	int to,next;
}edge[maxm];
struct Node{
	int id,dis;
	Node(int a=0,int b=0){id=a,dis=b;}
	bool operator < (const Node & x )const 
	{ return dis > x.dis ;}
};
int tot,head[maxn];
void Addedge(int x,int y){
	edge[++tot].to=y;
	edge[tot].next=head[x];
	head[x]=tot;
}

int n,m,x[maxm],y[maxm],s,t,dis[maxn];
bool v[maxn],vis[maxn];
priority_queue<Node> q;
queue<int> Q;

void Bfs(){
	Q.push(t);
	while(!Q.empty())
	{
		int temp = Q.front(); Q.pop();
		if(vis[temp])continue;
		vis[temp]=1;
		for(int i=head[temp];i;i=edge[i].next){
			if(!vis[edge[i].to])Q.push(edge[i].to);
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			v[i]=1;
			for(int j=head[i];j;j=edge[j].next){
				v[edge[j].to]=1;
			}
		}
	}
}

void Djs()
{	
	memset(dis,0x7f,sizeof(dis));
	dis[s]=0;q.push(Node(s,0));
	while(!q.empty()){
		Node u = q.top(); q.pop();
		if(v[u.id]||dis[u.id]!=u.dis)continue;
		for(int i=head[u.id];i;i=edge[i].next){
			if(!v[edge[i].to]&&dis[edge[i].to]>dis[u.id]+1){
				dis[edge[i].to]=dis[u.id]+1;
				q.push(Node(edge[i].to,dis[edge[i].to]));
			}
		}
	}
	if(dis[t] == 0x7f7f7f7f )dis[t]=-1;
	printf("%d\n",dis[t]);
}

int main(){
	freopen("roadb.in","r",stdin);
	freopen("roadb.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=m;i++){
		x[i]=read();y[i]=read();
		Addedge(y[i],x[i]);
	}
	s=read();t=read();
	Bfs();
	memset(edge,0,sizeof(edge)); memset(head,0,sizeof(head)); tot=0;
	for(int i=1;i<=m;i++)Addedge(x[i],y[i]);
	Djs();
	getchar();getchar();
}
/*
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5

3 2
1 2
2 1
1 3
*/