题解 P2296 【寻找道路】

· · 题解

看了几篇题解发现没有用两遍dijkstra的，那我就来水一发

首先读题：这个题的本质是找两点之间的最短路径，很容易想到dijkstra

但是在单源最短路的基础上，这个题加了一个限制条件：路径上的所有点的出边所指向的点都直接或间接与终点连通

这是什么意思呢？就是说在这条路径上，每一个节点的出边直接相连的所有节点都可以到达终点。

定义一个点的拓展为这一个节点的出边所连接的点的集合

换句话说，就是如果在这条路径上每一个点的拓展的集合有至少一个点不能到达终点，这条路径就是不合法的。

判断一个点是否能够到达终点，很容易就想到建反图，然后跑单源最短路。这样如果终点和这个点之间最短路径为inf，则证明这两个点不能互相到达

然后只需要正着来一遍dijkstra就行了。注意在进行的过程中，要判断一个点的拓展是否能够到达，也就是看反图上这个点和终点的距离

实际写起来也是比较简单的，主要就是CV大法

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=10005,M=200005,inf=0x7fffffff;
int n,m,s,t;
int head1[N],head2[N],cnt1,cnt2;
struct edge
{
    int to,dis,nxt;
}edg1[M],edg2[M];
void add1(int u,int v)
{
    edg1[++cnt1].dis=1;
    edg1[cnt1].to=v;
    edg1[cnt1].nxt=head1[u];
    head1[u]=cnt1;
}
void add2(int u,int v)
{
    edg2[++cnt2].dis=1;
    edg2[cnt2].to=v;
    edg2[cnt2].nxt=head2[u];
    head2[u]=cnt1;
}
int dis1[N],dis2[N];
bool vis1[N],vis2[N];

void dij2()
{
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    q.push(make_pair(0,t));
    for(int i=1;i<=n;i++) dis2[i]=inf;dis2[t]=0;
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(vis2[u]) continue;
        vis2[u]=1;
        for(int i=head2[u];i;i=edg2[i].nxt)
        {
            int v=edg2[i].to;
            if(dis2[u]+edg2[i].dis<dis2[v])
            {
                dis2[v]=dis2[u]+edg2[i].dis;
                q.push(make_pair(dis2[v],v));
            }
        }
    }
}

void dij1()
{
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    q.push(make_pair(0,s));
    for(int i=1;i<=n;i++) dis1[i]=inf;dis1[s]=0;
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(vis1[u]) continue;
        vis1[u]=1;
        for(int i=head1[u];i;i=edg1[i].nxt)
        {
            int v=edg1[i].to;bool flag=0;
            if(dis1[u]+edg1[i].dis<dis1[v]&&dis2[v]!=inf)
            {
                for(int j=head1[v];j;j=edg1[j].nxt)
                {
                    int v1=edg1[j].to;
                    if(dis2[v1]==inf) flag=1;
                }
                if(flag==1) continue;
                dis1[v]=dis1[u]+edg1[i].dis;
                q.push(make_pair(dis1[v],v));
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add1(u,v);
        add2(v,u);
    }
    scanf("%d%d",&s,&t);
    dij2();
    dij1();
    if(dis1[t]==inf) printf("-1\n");
    else printf("%d",dis1[t]);
}