题解 P2296 【寻找道路】

· · 题解

序言：

这道题真的很锻炼思维能力，就像其他几篇题解里说的那样，建议大家自己尝试着写一下，细节很多，真的很有意思。

正文：

题目链接：传送门

题目描述：

在有向图G中，每条边长度均为1，现给定起点和终点，请你在图中找出一条路径，该路径满足以下条件：

1.路径上的所有点的出边所指向的点都直接或间接与终点连通。

2.在满足1的条件下使路径更短

注意：图G中可能存在重边和自环，题目保证终点没有出边

请你输出符合条件的路径的长度

大致思路：

题目中已经说了每条边的边权均为1，故重边和自环不会造成任何影响，可忽略

因为边权固定，我们可以很轻易地想到用BFS求最短路的方法。因为在BFS中，节点 入队时会将整张图的节点分层，设起点的层数为0，则起点到终点的最短路径就是边权乘以层数

如图，若边权均为1，则起点（红色）到终点（蓝色）的距离为1x3=3

Code: 

void bfs_c(){
    while(p.size()){
        int v=p.front();p.pop();
        if(v==et)break;
        for(int i=hc[v];i;i=nc[i]){
            int x=vc[i];
            if(vis_c[x])continue;
            dist[x]=dist[v]+1;//统计层数
            p.push(x);vis_c[x]=1;
        }
    }
}

而对于处理题目中的条件一，我们可以采用反向建图+BFS的方式去寻找从终点出发能够到达的点并标记，则剩下没有被标记的点就是不与终点连通且不与终点间接连通的点，以样例二的图为例，反向建图并标记节点后：

如图，节点6就是不与终点连通或间接连通的点

按题目条件一要求，路径上的节点不能指向不与终点连通或不与重点间接连通的点

因此，在反向图中，未被标记的节点指向的所有节点均不满足条件，故将与未被标记的节点指向的所有的点的标记都清除，图为清除标记后：

此时在打好标记的节点（红圈）的正向图中进行BFS求最短路就可以求出最短的合法路径

具体做法&细节：

既然我们已经确定了大致的策略，下面我们来讨论一些题目的细节

1.题目中0<n<=10000，邻接矩阵肯定会超空间，可以使用邻接链表来储存

Code: 

const int N=100010,M=1000010;
int ver[M],Next[M],head[N],tot;
void add(int x,int y){
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}

2.第一次打的标记具有后效性，清除标记时不能直接清除第一次的标记

以图为例，1为起点4为终点：

反向建图并打标记后:

此时若枚举所有的节点，发现节点2不合法，将与节点2相连的节点3的标记清除，过后枚举到节点3时也会将与节点3相连的节点标记清除，这样得到的解是错误的。面对这种情况，我们可以开两个标记，枚举标记1清除标记2即可

3.第一次BFS打标记时不能以判断队首元素是否为起点作为BFS终止的条件

这就是卡了我一个小时的点，求巨佬们放过，别笑我。

为什么呢，因为题目要求的不是最短路径而是最短的合法路径，这样搜索会导致有些点没能来得及打上标记，无法得出正确解。

代码实现：

有了上面的铺垫，相信实现本题的代码对于大家来说一定不是一件难事吧

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=1000010;
int ver[M],Next[M],head[N],tot;
int vc[M],nc[M],hc[N],tc;
int n,m,st,et,dist[N];
bool vis[N],vis_c[N];//双标记 
queue<int> q,p;
void add(int x,int y){
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}//邻接表存反向图
void add_c(int x,int y){
    vc[++tc]=y,nc[tc]=hc[x],hc[x]=tc;
}//邻接表存正向图 
void bfs(){
    while(q.size()){
        int v=q.front();q.pop();
        for(int i=head[v];i;i=Next[i]){
            int x=ver[i];
            if(vis[x])continue;
            q.push(x);vis[x]=1;
        }
    }
}//第一遍搜索&&打标记 
void bfs_c(){
    while(p.size()){
        int v=p.front();p.pop();
        if(v==et)break;
        for(int i=hc[v];i;i=nc[i]){
            int x=vc[i];
            if(vis_c[x])continue;
            dist[x]=dist[v]+1;//统计层数 
            p.push(x);vis_c[x]=1;
        }
    }
}//第二遍搜索&&求最短路 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(y,x);add_c(x,y);//正反向分别建图 
    }
    scanf("%d%d",&st,&et);
    q.push(et);vis[et]=1;
    bfs();//第一次搜索 
    for(int u=1;u<=n;u++){//枚举节点清除标记 
        if(vis[u])continue;vis_c[u]=1;
        for(int i=head[u];i;i=Next[i]){
            int x=ver[i];
            vis_c[x]=1;
        }
    }
    p.push(st);vis_c[st]=1;
    bfs_c();//第二次搜索 
    if(dist[et]==0)puts("-1");
    else printf("%d\n",dist[et]);
    return 0;
}

结语：

希望大家能够独立完成此题&&有错误麻烦在评论区指正，谢谢

能给我个赞，把我顶到第一页么