描述
在有向图 G 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到 终点的路径，该路径满足以下条件：
路径上的所有点的出边所指向的点都直接或间接与终点连通。
在满足条件 1 的情况下使路径最短。
注意：图 G 中可能存在重边和自环，题目保证终点没有出边。 请你输出符合条件的路径的长度。
格式
输入格式
第一行有两个用一个空格隔开的整数 n 和 m，表示图有 n 个点和 m 条边。
接下来的 m 行每行 2 个整数 x、y，之间用一个空格隔开，表示有一条边从点 x 指向点y。
最后一行有两个用一个空格隔开的整数 s、t，表示起点为 s，终点为 t。
输出格式
输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。
如果这样的路径不存在，输出-1。
样例1
样例输入1[复制]
3 2
1 2
2 1
1 3
样例输出1[复制]
-1
样例2
样例输入2[复制]
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
样例输出2[复制]
3
限制
对于 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。
【题解】
把所有的边反向一下；
然后从终点进行dfs,预处理出哪些点可以到达终点；
然后枚举每一个点；看看是不是它所有的出边都能达到终点。有一个不能到达；这个点最后就不能被加入到最短路径中;
根据得到的信息正向进行spfa即可;
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#define lson L,m,rt<<1
#define rson m+1,R,rt<<1|1
#define LL long long
using namespace std;
const int MAXN = 1e4+100;
const int dx[5] = {0,1,-1,0,0};
const int dy[5] = {0,0,0,-1,1};
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
vector <int> zheng[MAXN],fan[MAXN];
int n,m,s,t,dis[MAXN];
bool bo[MAXN],can[MAXN];
queue <int> dl;
bool inque[MAXN];
void input_LL(LL &r)
{
r = 0;
char t = getchar();
while (!isdigit(t)) t = getchar();
LL sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
}
void input_int(int &r)
{
r = 0;
char t = getchar();
while (!isdigit(t)) t = getchar();
int sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
}
void dfs(int x)
{
bo[x] = true;
int len = fan[x].size();
for (int i = 0;i <= len-1;i++)
{
int y = fan[x][i];
if (!bo[y])
dfs(y);
}
}
int main()
{
input_int(n);input_int(m);
for (int i = 1;i <= m;i++)
{
int x,y;
input_int(x);input_int(y);
zheng[x].push_back(y);
fan[y].push_back(x);
}
input_int(s);input_int(t);
dfs(t);
for (int i = 1;i <= n;i++)
{
int len = zheng[i].size();
can[i] = true;
for (int j = 0;j <= len-1;j++)
{
int y = zheng[i][j];
if (!bo[y])
{
can[i] = false;
break;
}
}
}
memset(dis,INF,sizeof(dis));
dis[s] = 0;
dl.push(s);
inque[s] = true;
while (!dl.empty())
{
int x = dl.front();
dl.pop();
inque[x] = false;
int len = zheng[x].size();
for (int i = 0;i <= len-1;i++)
{
int y = zheng[x][i];
if (can[y] && dis[y]>dis[x]+1)
{
dis[y] = dis[x]+1;
if (!inque[y])
{
inque[y] = true;
dl.push(y);
}
}
}
}
if (dis[t]>=INF)
puts("-1");
else
printf("%d
",dis[t]);
return 0;
}