描述
在有向图 G 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到 终点的路径，该路径满足以下条件：
- 路径上的所有点的出边所指向的点都直接或间接与终点连通。
- 在满足条件 1 的情况下使路径最短。
注意：图 G 中可能存在重边和自环，题目保证终点没有出边。 请你输出符合条件的路径的长度。
格式
输入格式
第一行有两个用一个空格隔开的整数 n 和 m，表示图有 n 个点和 m 条边。
接下来的 m 行每行 2 个整数 x、y，之间用一个空格隔开，表示有一条边从点 x 指向点y。
最后一行有两个用一个空格隔开的整数 s、t，表示起点为 s，终点为 t。
输出格式
输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。
如果这样的路径不存在，输出-1。
限制
对于 30%的数据，0 < n ≤ 10，0 < m ≤ 20；
对于 60%的数据，0 < n ≤ 100，0 < m ≤ 2000；
对于 100%的数据，0 < n ≤ 10,000，0 < m ≤ 200,000，0 < x，y，s，t ≤ n，x ≠ t。
提示
【输入输出样例1说明】
如上图所示，箭头表示有向道路，圆点表示城市。起点 1 与终点 3 不连通，所以满足题目描述的路径不存在，故输出-1。
【输入输出样例2说明】
如上图所示，满足条件的路径为 1->3->4->5。注意点 2 不能在答案路径中，因为点 2 连了一条边到点 6，而点 6 不与终点 5 连通。
来源
NOIP2014 提高组 Day2
一开始错解题意了，以为只要是能到那些不连通终点的点的所有点都不能要，就全W了
后来才明白只用找和这些达不到终点的点直接相连的点就可以了，都是语文太差了。。。
方法很简单
就是先反向存图，从终点开始dfs一次把终点不能到的点标记出来
然后把所有和这些点直接相连的点也标记了，最后来一遍bfs
AC代码
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#define MAX 2000005
using namespace std;
int n,m;
int tot;
int s,t;
int ans;
int totz;
int v1,v2;
struct xx{int num,step;};
queue<xx>way;
int vis[];
int vis2[];
int innum[];
int cannot[];
int outnum[];//出度
int head[],next[MAX],tov[MAX];
int headz[],nextz[MAX],tovz[MAX];
void add(int a,int b)
{
tot++;
tov[tot]=b;
next[tot]=head[a];
head[a]=tot;
}
void addz(int a,int b)
{
totz++;
tovz[totz]=b;
nextz[totz]=headz[a];
headz[a]=tot;
}
void dfs(int k)
{
if(vis[k])return;
vis[k]=;
for(int i=head[k];i;i=next[i])
dfs(tov[i]);
}
void del(int k)
{
cannot[k]=;
for(int i=head[k];i;i=next[i])
if(!cannot[tov[i]])
cannot[tov[i]]=;
}
void BFS()
{
xx des,v,u;
des.num=s;
des.step=;
way.push(des);
while(!way.empty())
{
u=way.front();
way.pop();
for(int i=headz[u.num];i;i=nextz[i])
if(!vis2[tovz[i]]&&!cannot[tovz[i]])
{
v.num=tovz[i];
vis2[v.num]=;
v.step=u.step+;
if(v.num==t)
{
cout<<v.step;
exit();
}
way.push(v);
}
}
}
int main()
{
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
cin>>n>>m;
for(int i=;i<=m;i++)
{
scanf("%d%d",&v1,&v2);
if(v2!=v1)//自环
{
add(v2,v1);//反存边
addz(v1,v2);
outnum[v1]++;
innum[v2]++;
}
}
cin>>s>>t;
//if(s==t){cout<<"0";return 0;}
//if(outnum[s]==0||innum[t]==0){cout<<"-1";return 0;}
dfs(t);//从终点出发扩展一次找出不能直接或间接到终点的点
//if(!vis[s]){cout<<"-1";return 0;}
for(int i=;i<=n;i++)
if(!vis[i]&&!cannot[i])
del(i);
cannot[s]=;//起点必须可以走
BFS();
cout<<"-1";
return ;
}