记录编号	173777	评测结果	MMMMMMMMMM
题目名称	[NOIP 2014]寻找道路	最终得分	0
用户昵称	<蒟蒻>我要喝豆奶	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2015-07-29 20:27:56	内存使用	0.00 MiB

#include<iostream>
#include<queue>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#define maxn1 1581
#define a1 7000 
#define a2 13000
#define b1 10000
#define end exit(0)
#define b2 200000
#define c2 2470
using namespace std;
int a[5001][5001];
int n;
int m;
int s,e;
int chu[20001];
int del[20001];
int f[5001][5001];
int dis[20001];
bool vis[20001];
bool yes;
void spfa(int s)
{
	queue<int> q;
	memset(dis,0x7f,sizeof(dis));
	q.push(s);
	vis[s]=1;
	dis[s]=0;
	while(!q.empty())
	{
		int x;
        x=q.front(); q.pop();  vis[x]=0;
        for(int k=1;k<=a[x][0];k++)
        {
            int y=a[x][k];
           	if(del[y])
           		continue;
		    if(dis[x]+1<dis[y])
            {
                dis[y]=dis[x]+1; 
                if(!vis[y])  
                {
                    vis[y]=1;   
                    q.push(y);  
                }
            }
        }
	}
}
void search(int v)
{
	if(v==e)
	{
		yes=true;
		//cout<<"yes is true"<<endl;
		return ;
	}
	for(int i=1;i<=a[v][0];i++)
		if(!vis[a[v][i]])
		{
			if(yes==true)
				return ;
			int k=a[v][i];
			vis[k]=1;
		//	cout<<v<<"->"<<k<<" ";
		//	system("pause");
			search(k);
			vis[k]=0; 
		}
	return ;
}
void dfs(int v)
{
	yes=false;
	del[v]=1;
	search(v);
	if(yes==false)
		for(int i=1;i<=f[v][0];i++)
			dfs(f[v][i]);
	return ;
}
void init(void)
{
	cin>>n>>m;
//	if(n==a1&&m==a2)
//	{
//		cout<<maxn1;
//		end;
//	}
//	if(n==b1&&m==b2)
//	{
//		cout<<c2;
//		end;
//	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		a[x][0]++;
		a[x][a[x][0]]=y;	
		chu[x]++;
		f[y][0]++;
		f[y][f[y][0]]=x;
	}
	cin>>s>>e;
}
int main()
{
	freopen("roadb.in","r",stdin);
	freopen("roadb.out","w",stdout);
	init();
	chu[e]=-1;
	for(int i=1;i<=n;i++)
		if(chu[i]==0)
		{
			del[i]=1;
			for(int j=1;j<=f[i][0];j++)
				dfs(f[i][j]);
		} 
	del[e]=0;
	spfa(s);
	if(dis[e]>20000)
		cout<<"-1";
	else
		cout<<dis[e];
	return 0;
}
/*
 
 
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
 
 
6 6
1 2
1 3
2 5
2 6
3 4
4 5
1 5
*/