[NOIP2014]寻找道路

题目（vijos）
这题需要对原图进行重新构造。
首先，存图：因为要解决某个点是否能直接或间接与终点相连，所以我们对原图构一个反向图{e1}。当然，还要有一个原图{e2}。最后，我们还需要一个重构的图{e3}，这个重构的图是干嘛用的呢？往后看。
然后，对反向图{e1}从终点开始跑一遍spfa，用以记录哪些点可以直接或间接到达终点，保存在can数组里面。
然后，对{e2}开始重构图：从起点开始重新接边，如果这条边指向的点无法直接或间接到达终点，那么这条边就不加进去。如果可以，那么这条边就加进去。重新构好的图就保存在{e3}。
最后，对{e3}跑一遍spfa。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
const int INF=999999999;
using namespace std;
template <class ___E> inline void read(___E &e)
{
	e=0;bool ck=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')ck=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
	if(ck) e = -e;
}
int n,m;
int s,t;
struct edge{
	int vk;
	int next;
}e1[200005],e2[200005],e3[200005];
//e1反向图，e2原图，e3重构的图
int hd1[10005],hd2[10005],hd3[10005];
int k1=1,k2=1,k3=1;
int dis1[10005],dis2[10005];
bool vis[10005];
bool can[10005];
void ad1(int u,int v)
{
	e1[k1].vk=v;
	e1[k1].next=hd1[u];
	hd1[u]=k1++;
}
void ad2(int u,int v)
{
	e2[k2].vk=v;
	e2[k2].next=hd2[u];
	hd2[u]=k2++;
}
void ad3(int u,int v)
{
	e3[k3].vk=v;
	e3[k3].next=hd3[u];
	hd3[u]=k3++;
}
void sp1()
{
	queue <int> q;
	for (int i=1;i<=n;++i)
		dis1[i]=INF;
	dis1[t]=0;
	vis[t]=1;
	q.push(t);
	while (!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for (int i=hd1[u];i;i=e1[i].next)
		{
			int v=e1[i].vk;
			if (dis1[v]>dis1[u]+1)
			{
				dis1[v]=dis1[u]+1;
				if (!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
void sp2()
{
	queue <int> q;
	for (int i=1;i<=n;++i)
		dis2[i]=INF;
	dis2[s]=0;
	vis[s]=1;
	q.push(s);
	while (!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for (int i=hd3[u];i;i=e3[i].next)
		{
			int v=e3[i].vk;
			if (dis2[v]>dis2[u]+1)
			{
				dis2[v]=dis2[u]+1;
				if (!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
int main()
{
	read(n),read(m);
	for (register int i=1;i<=m;++i)
	{
		int x,y;
		read(x),read(y);
		ad1(y,x);
		ad2(x,y);
	}
	read(s),read(t);
	sp1();
	memset(vis,0,sizeof vis);
	for (register int i=1;i<=n;++i) can[i]=1;
	for (int k=1;k<=n;++k)
	{
		if (dis1[k]==INF)
		{
			for (int i=hd1[k];i;i=e1[i].next)
			{
				int v=e1[i].vk;
				can[v]=0;
			}
		}
	}
	for (int k=1;k<=n;++k)
	{
		for (int i=hd2[k];i;i=e2[i].next)
		{
			int v=e2[i].vk;
			if (can[v])
			{
				ad3(k,v);
			}
		}
	}
	sp2();
	if (dis2[t]==INF) printf("-1");
	else printf("%d",dis2[t]);
	return 0;
}