题解 P2296 【寻找道路】

· · 题解

两遍SPFA

（反向标记点 正向最短路）

是本蒟蒻第一篇题解了！（跟邹老板学写的）

题目描述

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

1.路径上的所有点的出边所指向的点都直接或间接与终点连通。 2.在满足条件 1 1的情况下使路径最短。

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

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

注意是不需要注意的

我们只看路径满足的条件：

第一点有点难理解，我们来看下面这张图

大家可能会对样例二中 2 这个点为什么不能用产生疑问

其实就是我

可以看出来：5 到不了 6 （用反向图跑），那么 2 的出边不与终点 5 相连，所以 2 也不可以包含在路径里

第二点就是正常的最短路了，相信大家都会，我选择用加过堆优化的spfa（~~其实就是dijisitra堆优化但是我们机房都管它叫spfa堆优化~~）

那就不废话了 上代码 里面有注释！！

#include <bits/stdc++.h>
#define I return
#define like 0
#define guanliyuan ;
using namespace std;

const int maxn=5000000;
struct node{
    int v,next;
}edge[maxn],edge1[maxn];
int head[maxn],head1[maxn],cnt,cnt1;
int n,m,s,t;
int dis[maxn],dis1[maxn],vis[maxn],vis1[maxn],bj[maxn];

struct cmp{
    bool operator()(int a,int b){
        return dis[a]>dis[b];
    }
};
struct cmp1{
    bool operator()(int a,int b){
        return dis1[a]>dis1[b];
    }
};
priority_queue<int,vector<int>,cmp> q;//两个队列堆优化！
priority_queue<int,vector<int>,cmp1> q1;//有无1要看清

void addedge(int u,int v){
    edge[++cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void addedge1(int u,int v){
    edge1[++cnt1].v=v;
    edge1[cnt1].next=head1[u];
    head1[u]=cnt1;
}

void spfa1(){
    memset(dis1,0x3f,sizeof(dis1));
    q1.push(t);
    dis1[t]=0;
    vis1[t]=1;
    while(!q1.empty()){
        int u=q1.top();
        q1.pop();
        vis[u]=0;
        for(int i=head1[u];i;i=edge1[i].next){
            int v=edge1[i].v;
            if(dis1[v]>dis1[u]+1){
                dis1[v]=dis1[u]+1;
                if(!vis1[v]){
                    q1.push(v);
                    vis1[v]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    if(dis1[i]==1061109567){//1061109567是手动复制memset出来的值！！
            bj[i]=1;//如果从终点到不了就把这个点标记，正向跑spfa
                //时不可用
        //再把这个点之前除了起外的点都标记（前面解释的很清楚了）
        for(int j=head1[i];j;j=edge1[j].next)
        if(edge1[j].v!=s) bj[edge1[j].v]=1;
    }
}

void spfa(){//正向spfa
    memset(dis,0x3f,sizeof(dis));
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty()){
        int u=q.top();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].v;
            if(bj[v]==1) continue;
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}

int main(){
    int a,b;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        addedge(a,b);//前向星建图，正反两遍
        addedge1(b,a);
    }
    scanf("%d%d",&s,&t);
    spfa1();//反向跑一边删点
    //for(int i=1;i<=n;i++)
    //cout<<bj[i]<<endl;
    if(bj[s]==1) cout<<"-1";//如果根本到不了起点，输出-1
    else{//可以到的话就跑一遍spfa 
        spfa();
        cout<<dis[t]<<endl;//输出最短距离
    } 
    I like guanliyuan//邹老板微操
}