题解 P2296 【寻找道路】

· · 题解

似乎没有dijstra堆优化的代码，在此来发一发。

实际上，这一题bfs即可，但是为了规范化，本人还是打了一个dijstra练最短路。

思路很简单，实际上就是从终点往回搜，若有搜不到的点，则与它相连的点都不能走。然后再最短路一发，就完了……

再简单介绍一下我的程序吧，STL队列，单调队列，邻接表，dijstra，就用这几个算法或数据结构，是什么相信大家已经非常了解了。

鉴于楼下各大神犇已经将思路的细节说得很清楚了，这里就不再补充了，直接上代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
int kd[500000]={0};
int head[500000]={0},tail[500000]={0};
int cnt=0;
struct Edge
{
    int t,w;
    int tnext;
    int hnext;
}edge[500000];//邻接表
inline void _insert(int a,int b)//邻接表插入边
{
    for(int i=head[a];i!=0;i=edge[i].hnext)//判重边，其实也没有什么必要
    {
        if(edge[i].w==b)
        {
            return;
        }
    }
    cnt++;
    edge[cnt].t=a;
    edge[cnt].w=b;
    edge[cnt].hnext=head[a];
    edge[cnt].tnext=tail[b];
    head[a]=tail[b]=cnt;//添加边
}
struct E
{
    int node,v;
};//优先队列结构体
struct cmp//优先队列比较结构体
{
    bool operator()(const E a,const E b)
    {
        return a.v>b.v;
    }
};
queue<int>arrive;//用于判断是否能到终点
bool visit[500000]={0};
int dis[500000];
bool cd[500000]={0};
inline int dy()//读入优化，防止卡常
{
    int shu=0;
    char c;
    c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')shu=shu*10+c-'0',c=getchar();
    return shu;
}
int main()
{
    int n,m;
    int s,e;
    int a,b;
    int lc;
    n=dy(),m=dy();
    for(int i=1;i<=n;i++)
    {
        dis[i]=2e9;
    }
    for(int i=0;i<m;i++)
    {
        a=dy(),b=dy();
        _insert(a,b);
    }
    s=dy(),e=dy();
    kd[e]=2;
    arrive.push(e);
    while(!arrive.empty())//搜遍所有能到终点的点
    {
        lc=arrive.front();
        if(!cd[lc])
        {
            cd[lc]=true;//已经搜到过，防止环
            for(int i=tail[lc];i!=0;i=edge[i].tnext)
            {
                lc=edge[i].t;
                kd[lc]=2;//kd==2即可以到达
                arrive.push(lc);
            }
        }
        arrive.pop();
    }
    for(int i=1;i<=n;i++)
    {
        if(!kd[i])//若不可到达，即kd==0
        {
            for(int j=tail[i];j!=0;j=edge[j].tnext)
            {
                lc=edge[j].t;
                kd[lc]=1;//注意不能赋值为0，要要赋值为1，否则便会无线的搜下去，背离了只往外拓展一层的目的
            }
        }
    }
    int curr=s;
    dis[curr]=0;
    priority_queue<E,vector<E>,cmp>dij;//dijstra优先队列
    E wl;
    wl.node=s,wl.v=0;
    dij.push(wl);
    while(!dij.empty())//dijstra主程序，如果看不懂，做做模板题，这里不详细讲述
    {
        curr=dij.top().node;
        dij.pop();
        if(visit[curr])continue;//已经为最短
        visit[curr]=true;
        for(int i=head[curr];i!=0;i=edge[i].hnext)
        {
            lc=edge[i].w;
            if(kd[lc]==2)//可以到达
            {
                if(dis[lc]>dis[curr]+1)
                {
                    dis[lc]=dis[curr]+1;
                    wl.node=lc,wl.v=dis[lc];
                    dij.push(wl);//更新
                }
            }
        }
    }
    if(curr==e)//已到达终点时curr不能再动了，所以直接这样判断
    {
        printf("%d",dis[e]);
    }
    else//记得判断
    {
        printf("-1");
    }
    return 0;
}