题解 P2296 【寻找道路】

aiyougege · 2018-04-17 16:19:32 · 题解

寻找道路

Solution

　　要求从起点到终点的一条路径上的点所到达的点都能到达终点.那么就可以先求出所有不能到达终点的点V.将能到达V的点删除, 然后求起点到终点的最短路.

• 可以从终点反向遍历, 能被遍历到的点就能到达终点, 用一个数组记录一个点能不能直接到达终点.这个要求我们提前建出反向边.
• 遍历一个点u所能到达的点v, 如果存在一个v不能直接到达终点, 说明这个点u不允许存在于所求路径上.因此就可以用一个数组记录这个点已经被从图中删除.
• 用最短路算法(如spfa)求出起点到终点的最短路, 如果遇到了已被标记删除的点就跳过这个点的更新.

Code

#include<cstring>
#include<cstdio>
#include<queue>
#define N 200005
#define inf 0x3f3f3f3f
using std::queue;

struct Edge{
    int v,nxt;
}e[N],E[N];

int n,m,s,t;
int head[N],tot;
int h[N],tol;

void AddEdge(int u,int v){
    e[++tot]=(Edge){v,head[u]};head[u]=tot;//正向边
    E[++tol]=(Edge){u,h[v]};h[v]=tol;//反向边
}

int vis[N];//表示这个点能直接到达终点
int be[N];//if be[i]== true 表示i没有被删除
int tt;

int dfs(int x,int f){//从终点开始反向遍历所有点
    vis[x]=true;
    for(int i=h[x];i;i=E[i].nxt){//反向边
        int to=E[i].v;
        if(to==f)continue;
        if(vis[to])continue;
        dfs(to,x);
    }
}

int init(){//删除不能存在于路径上的点
    for(int i=1;i<=n;++i){
        if(!vis[i])continue;bool flag=0;
        for(int j=head[i];j;j=e[j].nxt){
            int to=e[j].v;
            if(!vis[to])flag=true;//如果点 i 所到达的点
        }//       to 不能直接到达终点, 就删除这个点
        if(!flag)be[i]=true;
    }
}

int dis[N];

int spfa(int s,int t){// 从起点到终点的最短路
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    int top,to;
    dis[s]=0;queue<int>que;que.push(s);vis[s]=true;
    while(!que.empty()){
        top=que.front();
        que.pop();
        for(int i=head[top];i;i=e[i].nxt){
            to=e[i].v;
            if(!be[to])continue;//如果点 to           
            int l;//已被标记删除, 就跳过这个点的更新
            if(dis[top]+1<dis[to]){
                dis[to]=dis[top]+1;
                if(!vis[to]){
                    vis[to]=true;
                    que.push(to);
                }
            }
        }
    }
    return dis[t];
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
    }
    scanf("%d%d",&s,&t);
    dfs(t,0);
    init();
    int ans=spfa(s,t);
    if(ans==inf)ans=-1;
    printf("%d\n",ans);
    return 0;
}