链接：https://ac.nowcoder.com/acm/contest/23156/1005
来源：牛客网

题目描述

在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
1．路径上的所有点的出边所指向的点都直接或间接与终点连通。
2．在满足条件1的情况下使路径最短。

注意：图G中可能存在重边和自环，题目保证终点没有出边。

请你输出符合条件的路径的长度。

输入描述: 

第一行有两个用一个空格隔开的整数n和m，表示图有n个点和m条边。
接下来的m行每行2个整数x、y，之间用一个空格隔开，表示有一条边从点x指向点y。
最后一行有两个用一个空格隔开的整数s、t，表示起点为s，终点为t。

输出描述: 

输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出-1。
思路：看见求最短路径的题目-->用BFS求
先对终点求一遍BFS，求出所有能够到达起点的点，标记这些点，再遍历这些被标记的点，如果这些被标记的点的所有子节点（即节点的所有下一个点）有某个未被标记的点，则说明这个被标记的点不符合条件2，撤销标记。
再对起点求一遍BFS（此时BFS的对象是被标记的所有点），求最短路径即可。
注意存储图的时候可以开两个vector数组，一个存正向路，一个存反向路，方便起点与终点的BFS。

AC代码如下
#include<bits/stdc++.h>
using namespace std;
vector<int>mp[20020];
vector<int>a[20020];
int vis[20020];
vector<int>tp;
int n,m,x,y,st,ed,maxstep=-1;
struct node {
    int step,xt;
};
void BFS(int xt,int size) {
    queue<node>q;
    q.push(node {0,xt});
    if(size==1) {
        vis[xt]=1;
        while(!q.empty()) {
            node tmp=q.front();
            q.pop();
            for(auto i:a[tmp.xt]) { //相当于遍历a[tmp.xt]中的所有点
                if(vis[i]) continue;
                vis[i]=1;
                q.push(node {tmp.step+1,i});
            }
        }
    } else {
        vis[xt]=0;
        while(!q.empty()) {
            node tmp=q.front();
            q.pop();
            if(tmp.xt==ed) {
                maxstep=tmp.step;
                return;
            }
            for(auto i:mp[tmp.xt]) { //相当于遍历mp[tmp.xt]中的所有点
                if(!vis[i]) continue;
                vis[i]=0;
                q.push(node {tmp.step+1,i});
            }
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++) {
        scanf("%d%d",&x,&y);
        mp[x].push_back(y);
        a[y].push_back(x);
    }
    scanf("%d%d",&st,&ed);
    BFS(ed,1);
    for(int i=1; i<=n; i++) {
        if(!vis[i]) continue;
        for(auto j:mp[i]) {
            if(!vis[j]) {
                tp.push_back(i);
                break;
            }
        }
    }
    while(!tp.empty()) {
        vis[tp.back()]=0;
        tp.pop_back();
    }
    BFS(st,2);
    printf("%d\n",maxstep);
    return 0;
}