题解 P2296 【寻找道路】

shajjl · 2019-10-04 21:05:46 · 题解

本以为这题很难的……

使用dfs删点，dijkstra求最短路

这道题难想的地方在：

• 一个点A如果不能在最短路中，那么被这个点A直接或间接指向的点B的出度必然为0（去掉自环）或者这个点A不在能联通起点与终点的所有路径里

  比如样例2中的6号点：A，B情况都符合

  样例1中的2号点：符合A的情况

对于第二种情况，我们不需要有任何操作

因为这个点在dijkstra最短路中不会出现（因为它不与终点起点同时连通

那么我们专心来搞一下第一种情况

我用一个数组sumna在输入时记录每个点的出度，再枚举每个点，dfs出度为零的点

为什么要dfs

• 假如一个点A出度为0，那么指向它的所有点必然不能在最短路中出现，那么我们愉快地标记它就好咯。

  可是一个出度为一的点B，去掉A点后出度为0，那么所有指向它的点显然也不能出现在最短路中（因为B点没有直接或间接与终点相连，如样例2中2号点）一直深入，便dfs了

怎样dfs

• 如果一个点指向出度为0的点，就把他的出度-1，如果它的出度变为了0，就dfs它

void dfs(int x)
{
    for(int i=head2[x];i;i=e2[i].next)
    {   int v=e2[i].to;
        sumna[v]--;cvis[v]=true;if(sumna[v]==0)dfs(v);
    }
    return;
}

哦，我用**cvis**数组标记删除的点

为了dfs反向查找，我们还需要反向存边

void add(int x,int y)
{e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt;//正向
e2[++cnt2].to=x;e2[cnt2].next=head2[y];head2[y]=cnt2;}//反向

剩下的就很好办了

重边自环什么的

#include<iostream>//P2296
#include<cstdio>
#include<cstring>
#include<string>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#define ll long long
using namespace std;
const int INF=0x3FFFFFFF;
struct node
{int next,to;}e[200010],e2[200010];
int head[100010],head2[100010],n,m;
int cnt=0,cnt2=0,ed,st,sumna[100010],dis[100010];
void add(int x,int y)
{e[++cnt].to=y;e[cnt].next=head[x];head[x]=cnt;
e2[++cnt2].to=x;e2[cnt2].next=head2[y];head2[y]=cnt2;}
bool vis[100010],cvis[100010];
priority_queue<pair<int,int> > q;
void dfs(int x)
{
    for(int i=head2[x];i;i=e2[i].next)
    {   int v=e2[i].to;
        sumna[v]--;cvis[v]=true;if(sumna[v]==0)dfs(v);
    }
    return;
}
int main()
{
    int i,j,k;
    cin>>n>>m;memset(sumna,0,sizeof(sumna));
    for(i=1;i<=m;i++){cin>>j>>k;
    if(j==k)continue;//去除自环
    add(j,k);
    sumna[j]++;}//记录出度
    cin>>st>>ed;
    for(i=1;i<=n;i++)if(i!=ed&&!sumna[i])cvis[i]=true,dfs(i);

    //下面是堆优化的dijkstra板子
    fill(dis+1,dis+n+1,INF);
    dis[st]=0;
    q.push(make_pair(0,st));
    while(!q.empty())
    {
        int x=q.top().second;q.pop();
        if(vis[x])continue;
        vis[x]=true;
        for(i=head[x];i;i=e[i].next)
        {
            int y=e[i].to;if(cvis[y])continue;
            if(dis[y]>dis[x]+1)dis[y]=dis[x]+1,q.push(make_pair(-dis[y],y));
        }
    }
    if(dis[ed]==INF)cout<<-1;else cout<<dis[ed];
    return 0;
}

顺手留赞，感谢φ(>ω<*)