题解 P2296 【寻找道路】

· · 题解

打开题面看到“最短路径”马上就无脑打了dij

结果发现好像哪里不太对 好像不是普通最短路

但是 既然写了dij 那就尽量用吧

然后本菜鸡的这篇题解就出现了

第一遍dij

第二遍dij

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int maxn=10005;

const int maxm=200005;

int cnt,n,m,s,t;

int first[maxn],dis[maxn],u[maxm],v[maxm];

bool vis[maxn],b1[maxn],b2[maxn];

struct Edge
{
    int to,dis,nxt;
}a[maxm];

struct Node
{
    int num,dis;
};

inline int read()
{
    int p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+(c^48),c=getchar();}
    return p*f;
}

inline void addedge(int from,int to,int dis)
{
    a[++cnt]=(Edge){to,dis,first[from]};
    first[from]=cnt;
}

inline void init()
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        dis[i]=2147483647;
}

bool operator <(Node a,Node b)
{
    return a.dis>b.dis;
}

inline void dij(int s)
{
    init();
    priority_queue<Node>q;
    q.push((Node){s,0});
    dis[s]=0;
    while(!q.empty())
    {
        int u=q.top().num;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(register int i=first[u];i;i=a[i].nxt)
        {
            int v=a[i].to;
            if(b1[v]||b2[v]) continue;
            if(dis[v]>dis[u]+a[i].dis)
            {
                dis[v]=dis[u]+a[i].dis;
                q.push((Node){v,dis[v]});
            }
        }
    }
}

int main()
{
    n=read(),m=read();
    for(register int i=1;i<=m;i++)
    {
        u[i]=read(),v[i]=read();
        if(u[i]==v[i]) continue;
        addedge(v[i],u[i],1);
    }
    s=read(),t=read();
    dij(t);
    for(register int i=1;i<=n;i++)
        if(dis[i]==2147483647)
        {
            b1[i]=1;
            for(register int j=first[i];j;j=a[j].nxt)
                b2[a[j].to]=1;//尽量用另一个数组存，否则有后效性
        }
    memset(a,0,sizeof(a));
    memset(first,0,sizeof(first));
    cnt=0;
    for(register int i=1;i<=m;i++)
    {
        if(u[i]==v[i]) continue;
        addedge(u[i],v[i],1);
    }   
    dij(s); 
    if(dis[t]==2147483647) cout<<"-1";
    else cout<<dis[t];
    return 0;
}