记录编号	486083	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]寻找道路	最终得分	100
用户昵称	+1s	是否通过	通过
代码语言	C++	运行时间	0.088 s
提交时间	2018-02-05 10:26:22	内存使用	0.58 MiB

#include<cstdio>
#include<queue>
#include<cstring>
int n,m,s,t,vsd[10010],active[10010],dph[10010],fl;
std::vector<int> arc[10010],arcback[10010];
void bfsback()
{
	std::queue<int> q;
	q.push(t);
	while(!q.empty())
	{
		int tp=q.front();
		q.pop();
		vsd[tp]=1;
		active[tp]=1;
		for(std::vector<int>::iterator it=arcback[tp].begin();it!=arcback[tp].end();it++)
		if(vsd[*it]==0)
		{
			q.push(*it);
			vsd[*it]=1;
			active[*it]=1;
		}
	}
}
void bfsforward()
{
	std::queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int tp=q.front();
		q.pop();
		vsd[tp]=1;
		for(std::vector<int>::iterator it=arc[tp].begin();it!=arc[tp].end();it++)
		if(vsd[*it]==0)
		if(active[*it]==0)active[tp]=0;
		else
		{
			q.push(*it);
			vsd[*it]=1;
		}
	}
}
void bfs()
{
	std::queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int tp=q.front();
		q.pop();
		vsd[tp]=1;
		if(tp==t)
		{
			fl=1;
			return;
		}
		for(std::vector<int>::iterator it=arc[tp].begin();it!=arc[tp].end();it++)
		if(vsd[*it]==0&&active[*it]==1)
		{
			q.push(*it);
			vsd[*it]=1;
			dph[*it]=dph[tp]+1;
		}
	}
	fl=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++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		arc[x].push_back(y);
		arcback[y].push_back(x);
	}
	scanf("%d %d",&s,&t);
	bfsback();
	memset(vsd,0,sizeof vsd);
	bfsforward();
	memset(vsd,0,sizeof vsd);
	if(active[s]==0)printf("-1");
	else
	{
		bfs();
		if(fl==1)printf("%d",dph[t]);
		else printf("-1");
	}
	return 0;
}