【DFS】NOIP2014]寻找道路

亦凉 2024-03-24 09:32 68阅读 0赞

[1005-\[NOIP2014\]寻找道路\_2021秋季算法入门班第六章习题：搜索与搜索剪枝（重现赛）@lamentropetion (nowcoder.com)][1005-_NOIP2014_2021_lamentropetion _nowcoder.com]

题意：

![12e5e9888ac64303a554154d89ff0add.png][]

思路：

先建个反图来check每个点到终点的连通性，用can数组存一下

然后去bfs，bfs保证了最短路，因为边权都是1，所以可以直接bfs

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e4+10,mxe=2e5+10,mnf=0x3f3f3f3f;
    struct ty{
        int to,next;
    }edge[mxe<<1],fedge[mxe<<1];
    queue<int> q,fq;
    int n,m,x,y,s,t,ok=1,cnt=0,fcnt=0;
    int head[mxn],fhead[mxn],dis[mxn],vis[mxn],can[mxn];
    void init(){
        cnt=fcnt=0,ok=1;
        for(int i=0;i<=n;i++){
            vis[i]=can[i]=0;
            head[i]=fhead[i]=-1;
            dis[i]=mnf;
        }
    }
    void add(int u,int v){
        edge[cnt].to=v;
        edge[cnt].next=head[u];
        head[u]=cnt++;
    }
    void fadd(int u,int v){
        fedge[fcnt].to=v;
        fedge[fcnt].next=fhead[u];
        fhead[u]=fcnt++;
    }
    void bfs(){
        q.push(s);dis[s]=0;vis[s]=1;
        while(!q.empty()){
            int tmp=q.front();
            q.pop();
            for(int i=head[tmp];~i;i=edge[i].next){
                if(!vis[edge[i].to]){
                    ok=1;
                    for(int j=head[edge[i].to];~j;j=edge[j].next){
                        if(!can[edge[j].to]) ok=0;
                    }
                    if(ok){
                        dis[edge[i].to]=dis[tmp]+1;
                        vis[edge[i].to]=1;
                        q.push(edge[i].to);
                    }
                }
            }
        }
    }
    void fbfs(){
        fq.push(t);vis[t]=1;can[t]=1;
        while(!fq.empty()){
            int tmp=fq.front();
            fq.pop();
            for(int i=fhead[tmp];~i;i=fedge[i].next){
                if(!vis[fedge[i].to]){
                    can[fedge[i].to]=1;
                    vis[fedge[i].to]=1;
                    fq.push(fedge[i].to);
                }
            }
        }
    }
    int main(){
        scanf("%d%d",&n,&m);
        init();
        for(int i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            add(x,y);
            fadd(y,x);
        }
        scanf("%d%d",&s,&t);
        fbfs();
        for(int i=0;i<=n;i++){
            vis[i]=0;
        }
        bfs();
        //for(int i=1;i<=n;i++) printf("%d%c",can[i],i==n?'\n':' ');
        printf("%d",dis[t]==mnf?-1:dis[t]);
        return 0;
    }

[1005-_NOIP2014_2021_lamentropetion _nowcoder.com]: https://ac.nowcoder.com/acm/contest/54516/1005
[12e5e9888ac64303a554154d89ff0add.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/a78b9e7b4e2843fba19b0bc3361c843f.png