P2296 [NOIP2014 提高组] 寻找道路，转载题解

此答案为我抄的，竟然没做出来（真无耻），为了借鉴学习（其实是为了凑AC）

在此附上链接：题解链接https://www.luogu.com.cn/blog/shaoping/solution-p2296
题目链接：https://www.luogu.com.cn/problem/P2296

#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
bool inroad[10010],can[10010];       //inroad 表示此点是否可以出现在路径上  can 表示此点是否可以到达终点 
int dis[10010];                      //dis 表示此点距离起点的距离 
vector<int>side[10010];              //正向建边 
vector<int>edis[10010];              //反向建边 
int main()
{
    int n,m,a,b,s,t;
    cin>>n>>m;
    for(int i=1;i<=m;i++)            //读入并正反向建边 
    {
        cin>>a>>b;
        side[a].push_back(b);
        edis[b].push_back(a);
    }
    cin>>s>>t;
    can[t]=1;                        //终点先设置为 1 
    queue<int>que; 
    que.push(t);
    while(!que.empty())              //从终点反向查找② 
    {
        int now=que.front();
        que.pop();
        for(int i=edis[now].size()-1;i>=0;i--)
        {
            int to=edis[now][i];
            if(!can[to])
            {
                que.push(to);   
                can[to]=1;
            }
        }
    }
    if(!can[s])         //起点无法到达终点就直接结束程序 
    {
        cout<<"-1";
        return 0;
    }
    for(int i=1;i<=n;i++)       //判断哪些点是①
    {
        if(can[i])
        {
            inroad[i]=1;
            for(int j=side[i].size()-1;j>=0;j--)    //遍历所有的边 
            {
                int to=side[i][j];
                if(!can[to])            //如果它出边所到达的点无法到达终点,这个点就不可以出现在路径上 
                {
                    inroad[i]=0;
                    break;
                }
            }
        }
    }
    if(!inroad[s])			            //这里需要特殊判定一下起点是否满足条件，感谢 @WestTree 的HACK		
    {
    	cout<<"-1";
    	return 0;
        }
    dis[s]=1;que.push(s);
    while(!que.empty())                 //从起点bfs，只经过①点，找出最短距离 
    {
        int now=que.front();
        que.pop();
        if(now==t)                  //到达终点,输出结果 
        {
            cout<<dis[t]-1;
            return 0;
        }
        for(int i=side[now].size()-1;i>=0;i--)
        {
            int to=side[now][i];
            if(inroad[to]&&!dis[to])
            {
                dis[to]=dis[now]+1;
                que.push(to);
            }
        }
    }
    cout<<"-1";                     //否则还是无法到达 
}