题解 P2296 【寻找道路】

· · 题解

所有边边权一样，所以我们用bfs就能求（何况本蒟蒻觉得dij很难写）
首先，这里有的点不能走，那么我们只要把这些点去掉即可
怎么去掉呢？总不能把每一个点都跑一遍bfs吧......
反着从终点开始跑，只需要反向建图，不仅可以省去大量时间，而且因为数据比较小，不会炸
反向跑之后标出所有可以走的点，再正向跑一次即可 

#include<bits/stdc++.h>
using namespace std;
int n,m,start,end;
bool lian[10000],cu[10000];
vector<int> path[10000],fanpath[10000];
struct qu
{
    int ni,w;
};
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int st,ed;
        cin>>st>>ed;
        path[st].push_back(ed);
        fanpath[ed].push_back(st);
    }
    cin>>start>>end;
    memset(lian,false,sizeof(lian));
    memset(cu,true,sizeof(cu));
    //反向 
    queue<int> q1;
    q1.push(end);
    while(!q1.empty())
    {
        int now=q1.front();
        q1.pop();
        lian[now]=true;
        for(int i=0;i<fanpath[now].size();i++)
            q1.push(fanpath[now][i]);
    }
    if(!lian[start])
    {
        cout<<-1<<endl;
        return 0;
    }
    //处理 
    for(int i=1;i<=n;i++)
        for(int j=0;j<path[i].size();j++)
            if(!lian[i]||!lian[path[i][j]])
                cu[i]=false;
    //正向 
    queue<qu> q2;
    q2.push(qu{start,0});
    while(!q2.empty())
    {
        int now=q2.front().ni,wei=q2.front().w;
        q2.pop();
        if(now==end)
        {
            cout<<wei<<endl;
            return 0;
        }
        for(int i=0;i<path[now].size();i++)
            if(cu[path[now][i]])
                q2.push(qu{path[now][i],wei+1});
    }
}

蒟蒻坚持己见觉得这是最简单的方法并且不接受反驳