题解 P2296 【寻找道路】

· · 题解

感觉思路不需要解释了

这道题主要是要从后往前逆向思考——从终点便利一遍，遍历不到的点就是不合法的点

所以我们从终点一次bfs处理出这些不合法的点，然后一遍最短路就可以A掉辣

我认为我的代码很好懂就是有点长 不过写起来好像比楼上的DALAO们方便

//

#include<bits/stdc++.h>

using namespace std;

const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;

int n,m,s,t;
int head[MAXN],ver[MAXN],edge[MAXN],next[MAXN];//正的前向星
int cnt;
int rhead[MAXN],rver[MAXN],redge[MAXN],rnext[MAXN];//反的前向星
int rcnt;
bool vis[MAXN],rvis[MAXN];//所有带r的都是反的……
int d[MAXN];

queue<int> rq;
priority_queue<pair<int,int> > q;

inline void add(int x,int y,int w)//正向存边
{
    ++cnt;

    ver[cnt]=y,edge[cnt]=w,next[cnt]=head[x],head[x]=cnt;
}

inline void radd(int x,int y,int w)//反向存边
{
    ++rcnt;

    rver[rcnt]=y,redge[rcnt]=w,rnext[cnt]=rhead[x],rhead[x]=rcnt;
}

inline void bfs(int t)
{
    memset(rvis,0,sizeof(rvis));

    rq.push(t);
    rvis[t]=1;

    while(!rq.empty())
    {
        int u=rq.front();
        rq.pop();

//      cout<<u<<endl;

//      cout<<u<<" "<<rvis[u]<<endl;

        for(int i=rhead[u];i;i=rnext[i])
        {
            int y=rver[i];

//          cout<<y<<" "<<rvis[y]<<endl;

            if(rvis[y])continue;

            rvis[y]=1;
            rq.push(y);
        }
    }
}

inline void dijkstra(int s)
{
    memset(d,INF,sizeof(d));
    memset(vis,0,sizeof(vis));

    d[s]=0;
    q.push(make_pair(-d[s],s));

    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();

        if(vis[u])continue;

        vis[u]=1;

        for(int i=head[u];i;i=next[i])
        {
            int y=ver[i],w=edge[i];

            /*---------------------------*/
            bool flag=1;
            for(int j=head[y];j;j=next[j])
            {
                int y2=ver[j];

                if(!rvis[y2])flag=0;
            }
            if(!flag)continue;
            //对每个点处理：如果出度指向的点没有被遍历到，说明这个点不合法
            /*---------------------------*/

            if(vis[y])continue;
            if(!rvis[y])continue;//稳妥一点

            if(d[y]>d[u]+w)
            {
                d[y]=d[u]+w;
                q.push(make_pair(-d[y],y));
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin>>n>>m;

    int x,y;

    for(int i=1;i<=m;++i)
    {
        cin>>x>>y;

        add(x,y,1);
        radd(y,x,1);
    }

    cin>>s>>t;

    bfs(t);

//  for(int i=1;i<=n;++i)
//      cout<<rvis[i]<<endl;

    dijkstra(s);

    if(d[t]==INF)d[t]=-1;
    cout<<d[t]<<endl;

    return 0;
}