记录编号	466405	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]寻找道路	最终得分	100
用户昵称	据说这是zzy	是否通过	通过
代码语言	C++	运行时间	0.107 s
提交时间	2017-10-28 22:16:11	内存使用	1.04 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<deque>
using namespace std;
deque <int> d;
bool v[20000]={0};//访问 
bool nf[20000]={0};//判断是否可以访问
int spa[20000];
int n=0,m=0,s=0,t=0;
struct abc
{
	vector<int> q;
	int sl;
}a[20005];
struct bcd
{
	vector<int> o;
	int ss;
}b[20005];
int spfa(int x)//最短路
{
	d.push_back(x);
	while(d.size()!=0)
	{
     		int u=d.front(); 
		d.pop_front();
		v[u]=0;
	for(int i=0;i<a[u].sl;i++) 
		{
			if(v[a[u].q[i]]!=1&&!nf[a[u].q[i]])//队列中是否还有重复的
			{
				if(1+spa[u]<spa[a[u].q[i]]&&!nf[a[u].q[i]])
				{
					spa[a[u].q[i]]=1+spa[u];
					d.push_back(a[u].q[i]);
					v[a[u].q[i]]=1;
				}
			}
		}
	}
}
int bbfs(int x,int n)//第一遍
{
	d.push_back(x);
	v[x]=1;
	while(d.size()!=0)
	{
		int u=d.front(); 
		d.pop_front();
		for(int i=0;i<b[u].ss;i++)
		{
			if(!v[b[u].o[i]]&&b[u].o[i])
			{
				d.push_back(b[u].o[i]);
				v[b[u].o[i]]=1;
			} 
		}
		
	}
}
int sc(int n)//判读函数
{
	for(int i=1;i<=n;i++)
	{
		if(v[i]!=1)
		{
			nf[i]=1;
		for(int j=0;j<b[i].ss;j++)
			nf[b[i].o[j]]=1;
		}
	}
}
int main()
{
	freopen("roadb.in","r",stdin);
	freopen("roadb.out","w",stdout);	
	int n,m,s,t;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x=0,y=0;
		scanf("%d%d",&x,&y);
		a[x].q.push_back(y);
		a[x].sl++;
		b[y].o.push_back(x);
		b[y].ss ++;
	}
	cin>>s>>t;
	bbfs(t,n);
	sc(n);
	for(int i=1;i<=n;i++)
	{
		v[i]=0;
		spa[i]=9999;
	}
	spa[s]=0;
	spfa(s);
	if(spa[t]==9999)
		cout<<-1;
	else
	cout<<spa[t];
}