题解 P2296 【寻找道路】

WNico · 2019-10-21 20:08:08 · 题解

这是一道有点让我难受的题

虽然其实很简单

题意

在一个只保证终点没有出边的，且边权均为 0 的有向图上求最短路

但是这条路经过的每一个点必须满足，它的每一条出边连接的点都可以到达终点

似乎很麻烦（我描述能力不太行

题目中的图也可以很好的给你提示

解法

最短路的话用什么都可以（bfs 或 dij

题目的重点在于找出这些不能经过的点

既然一个点到不了终点，那么从终点倒着走，也到不了这些点

建反图深搜即可（不太懂为什么dalao们都用的是bfs

inline void dfs(int x){     // rab 是标记数组
    if(rab[x]) return;      // 遇上环便返回
    rab[x]=1;
    for(int i=hear[x];i;i=rxt[i]){
        dfs(ro[i]);
    }                       // 不去除标记，可以得到终点可以到达的点
}

然后对每个点拓展它的边

for(int i=1;i<=n;++i){      // 遍历每个点
    tret[i]=1;
    for(int j=head[i];j;j=nxt[j])   // 遍历每个点的出边
        if(rab[to[j]]==0){
            tret[i]=0;      // 如果出边中有无法到达的点，标记这个点不可经过
            break;
        }
}

然后简单的spfa

上代码

#include<bits/stdc++·h>
using namespace std;

const int N = 10009,M = 200009,inf = 1061109567;
int n,m,s,t;
int head[N],nxt[M],to[M],tl=0;          // 正边
int hear[N],rxt[M],ro[M],rl=0;          // 反边
int dis[N];
//bitset<N> used,rab,hdb,tret;          // 为什么要这么起变量名？我也不知道
bool rab[N],tret[N];                    // tret数组标记不能经过的点
                                        // rab数组标记能到达终点的点
inline int read(){
    int s=0,w=1;char ch;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') w=-1;
    while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
    return s*w;
}

inline void adde(int x,int y){          // 建正边
    to[++tl]=y;nxt[tl]=head[x];head[x]=tl;
}
inline void addr(int x,int y){          // 建反边
    ro[++rl]=y;rxt[rl]=hear[x];hear[x]=rl;
}

inline int _spfa(){
    queue<int> spfa;
    memset(dis,0x3f,sizeof(dis));
    spfa.push(s);
    dis[s]=0;
    while(!spfa.empty()){
        int w=spfa.front();spfa.pop();
        for(int i=head[w];i;i=nxt[i]){
            if(dis[to[i]]>dis[w]+1&&tret[to[i]]){
                dis[to[i]] = dis[w]+1;
                spfa.push(to[i]); 
            }
        }
    }
    return dis[t]==inf?-1:dis[t];
}

/*
inline int dfs(int x){              // 尝试正向记忆化搜索的遗骸
    if(used[x]) return -1;          // 该怎么做就怎么做，不要想桃子
    if(hdb[x]) return rab[x];
    used[x]=1;
    int ret=-1;
    for(int i=head[x];i;i=nxt[i]){
        int j=dfs(to[i]);
        if(j==1) ret=1;
        if(j==0&&ret==-1) ret=0;
    }
    used[x]=0;
    if(ret!=-1) hdb[x]=1,rab[x]=ret;
    return ret;
}
*/

inline void dfs(int x){
    if(rab[x]) return;
    rab[x]=1;
    for(int i=hear[x];i;i=rxt[i]){
        dfs(ro[i]);
    }
}

int main(){
    n=read(),m=read();
    for(int i=1,x,y;i<=m;++i){
        x=read(),y=read();
        adde(x,y);addr(y,x);
    }
    s=read(),t=read();
    dfs(t);
    if(rab[s]==0){                  // 特判到不了（其实没有必要
        cout<<-1;
        return 0;
    }else{
        for(int i=1;i<=n;++i){
            tret[i]=1;
            for(int j=head[i];j;j=nxt[j])
                if(rab[to[j]]==0){
                    tret[i]=0;
                    break;
                }
        }
        cout<<_spfa();
    }
    return 0;
}