题目描述

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

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

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

输入描述:

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

输出描述:

输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出-1。

示例1

输入
3 2
1 2
2 1
1 3
输出
-1
说明

如上图所示，箭头表示有向道路，圆点表示城市。起点1与终点3不连通，所以满足题目描述的路径不存在，故输出-1。

示例2

输入
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
输出
3
说明

如上图所示，满足条件的路径为1->3->4->5。注意点2不能在答案路径中，因为点2连了一条边到点6，而点6不与终点5连通。

备注

对于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。

解答

首先，预处理，把每条边反向。

从终点开始bfs，标记从终点开始可以走到的点。

第二步，枚举每一个点，如果这个点没有被标记，则枚举它的每一条出边（反向后的），如果它指向的点被标记，则说明这个被标记的点不合法，删除。

第三步，在合法点上bfs，单源最短路。找到答案。详见代码： 

#include<bits/stdc++.h>
using namespace std;
int read()
{
    int x=0,y=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='0')y=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*y;
}
int n,m;
vector<int>v[10005];
bool cando[10005],er[10005];
queue<int>q;
int st,ed;
int ans[10005];
int main()
{    
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int a=read(),b=read();
        if(a==b)continue;//去除自环
        v[b].push_back(a);
    }
    st=read(),ed=read();
    cando[ed]=1;//第一遍bfs
    q.push(ed);
    while(!q.empty())
    {
        int no=q.front();
        q.pop();
        for(int i=0,j=v[no].size();i<j;i++)
            if(!cando[v[no][i]]){cando[v[no][i]]=1;q.push(v[no][i]);}//标记从终点可以到达的点
    }
    memcpy(er,cando,sizeof(cando));//准备第二次标记
        //注意这里最好有第二个数组标记，在一个数组里删点有后效型，如果一个点开始被标记，它通过一个序号比它小的点删除了，
       //那么访问到它的时候，就会被当成开始就没被标记的点，会通过它把合法点删除。
      //这样做完之后，合法点都被标记了。
    for(int i=1;i<=n;i++)
        if(!cando[i])
            for(int j=0,k=v[i].size();j<k;j++)
                if(er[v[i][j]])
                    er[v[i][j]]=0;
        //最后一遍bfs找答案。
    q.push(ed);
    while(!q.empty())
    {
        int no=q.front();
        q.pop();
        for(int i=0,j=v[no].size();i<j;i++)
            if(er[v[no][i]])
            {
                q.push(v[no][i]);
                er[v[no][i]]=0;
                ans[v[no][i]]=ans[no]+1;
            }
    }
       //题目要求输出。
    if(ans[st]==0)printf("-1");
    else printf("%d",ans[st]);
    return 0;
}


来源：_空_