记录编号	201119	评测结果	AAAAAAAAAA
题目名称	[NOIP 2014]寻找道路	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.045 s
提交时间	2015-10-29 21:44:21	内存使用	7.31 MiB

#include<cstdio>
#include<cstring>
int EPX,n,m;
inline void in(int &TEMP)
{
	for(TEMP=getchar();TEMP<48||TEMP>57;TEMP=getchar());
	TEMP^=48;
	for(EPX=getchar();EPX<58&&EPX>47;EPX=getchar())
		TEMP=(TEMP<<3)+(TEMP<<1)+(EPX^48);
}
int u,v,shu,first[10100],sh,firs[10100];
struct bian
{
	int v,next;
}o[200100],e[200100];
inline void add(int u,int v)
{
 	 o[++shu].v=v;
 	 o[shu].next=first[u];
 	 first[u]=shu;
}
inline void ad(int u,int v)
{
 	 e[++sh].v=v;
 	 e[sh].next=firs[u];
 	 firs[u]=sh;
}
int s,t;
bool flag[10100];
bool FLAG[10100];
inline void dfs(int x)
{
	flag[x]=1;
	for(int i=firs[x];i;i=e[i].next)
	    if(!flag[e[i].v])
	    	dfs(e[i].v);
}
int l,r,q[1001000],d[10100];
bool p[10100];
void spfa()
{
	memset(d,0x3f,sizeof(d));
	q[0]=s;
	d[s]=0;
	while(l<=r)
	{
		u=q[l++];
		p[u]=0;
		for(int i=first[u];i;i=o[i].next)
		    if(!FLAG[o[i].v]&&d[o[i].v]>d[u]+1)
		    {
				d[o[i].v]=d[u]+1;
				if(!p[o[i].v])
				{
					p[o[i].v]=1;
					q[++r]=o[i].v;
				}
		    }
	}
}
int main()
{
	freopen("roadb.in","r",stdin);
	freopen("roadb.out","w",stdout);
	in(n),in(m);
	while(m--)
	{
		in(u),in(v);
		add(u,v);
		ad(v,u);
	}
	in(s),in(t);
	dfs(t);
	for(int i=1;i<=n;++i)
	    if(!flag[i])
	    {
			FLAG[i]=1;
			for(int j=firs[i];j;j=e[j].next)
	            FLAG[e[j].v]=1;
		}
	spfa();
	if(d[t]>1000000000)
	    puts("-1");
	else
		printf("%d",d[t]);
	//while(1);
}