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

川长思鸟来 2022-10-28 10:14 181阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 4]  
此答案为我抄的，竟然没做出来（真无耻），为了借鉴学习（其实是为了凑AC）

在此附上链接：题解链接[https://www.luogu.com.cn/blog/shaoping/solution-p2296][https_www.luogu.com.cn_blog_shaoping_solution-p2296]  
题目链接：[https://www.luogu.com.cn/problem/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";                     //否则还是无法到达 
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/440809226c6048989b0aad8ceb0c5caa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221024/87dac0e6f4574c4792781957d3612648.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221024/a4b958743cce4d5d851735d83627aa90.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221024/e6dcdfe9d82e4f04916d2822898d9789.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221024/469f44b9866e46beb9b54f4478232f72.png
[https_www.luogu.com.cn_blog_shaoping_solution-p2296]: https://www.luogu.com.cn/blog/shaoping/solution-p2296
[https_www.luogu.com.cn_problem_P2296]: https://www.luogu.com.cn/problem/P2296