题目简要介绍

找到一条能从起点到终点的路径同时满足以下要求：

1. 路径所经过的所有点（和这些点指向的点）都直接或间接指向终点
2. 最短路径

思路

起初我看到最短路所以直接选择了bfs,但疏于对题目的理解只判断了这个点能否直接或间接到达终点，必须要判断这个点是否是有效点

自我感觉学到的

利用反向图来判断这个点能否直接或间接地到达终点（也能使用dfs来判断，从终点出发）

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[10100]; //用于标记正向的的方向
vector<int> rg[10100]; //用于标记反向的方向
int dist[10010]; //记录距离&&是否走过
bool canReachEnd[10010]; //记录哪些点能直接或间接地到达终点
bool vail[10010]; //标记是否是有效点->所指向的所有点能否直接或间接地指向终点 
                                    //不能只判断这个点



//利用反向图检查从终点所能到达的点（也就是 能直接或者间接到达终点的点）

void CanEndbfs(int e){
    canReachEnd[e]=true;
    queue<int>q;
    q.push(e);
    while(!q.empty()){
        int it=q.front();
        q.pop();
        for(int next:rg[it]){
            if(!canReachEnd[next]){
                canReachEnd[next]=true;
                q.push(next);
            }
        }
    }
}
 
 
int bfs(int s,int e){
    if(!vail[s]) return -1;
    
    memset(dist,-1,sizeof(dist));
    dist[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int it=q.front();
        q.pop();
        if(it==e) return dist[it];
        for(int next:g[it]){
            if(vail[next]&&dist[next]==-1){
                dist[next]=dist[it]+1;
                q.push(next);
            }
        }
    }
    return -1;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        rg[y].push_back(x);
    }
    int s,t;
    cin>>s>>t;
    CanEndbfs(t);
    
    
    //然而只判断某个点是否能到达重点是完全不够的
    //还要检查这个能到达终点的点所指向的所有点能否到达终点
    //如果有至少一个点无法到达 那么这个点就是无效点
    
    for(int i=1;i<=n;++i){
        if(canReachEnd[i])
            vail[i]=true;
        for(int next:g[i]){
            if(!canReachEnd[next])
                vail[i]=false;
        }
    }
    
    cout<<bfs(s,t)<<endl;
    return 0;
}