AC日记——逃离僵尸岛 洛谷 P3393

逃离僵尸岛

思路：

　　spfa；

代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 200005

#define maxque 1800056

#define INF 1e12

#define ll long long

ll n,m,E[maxque],V[maxque],cnt,head[maxn],dis[maxn];

ll que[maxque],k,s,tag[maxn],Q,P,val[maxn];

bool if_[maxn];

inline void in(ll &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

inline void edge_add(ll u,ll v)

{

    E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;

    E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;

}

void spfa1()

{

    ll h=,tail=,pos,u,v;

    memset(if_,,sizeof(if_));

    for(int i=;i<=n;i++) tag[i]=INF;

    for(ll i=;i<=k;i++) in(pos),que[tail++]=pos,tag[pos]=,if_[pos]=true;

    for(ll i=;i<=m;i++) in(u),in(v),edge_add(u,v);

    while(h<tail)

    {

        ll now=que[h++];if_[now]=false;

        for(ll i=head[now];i;i=E[i])

        {

            if(tag[now]+<tag[V[i]])

            {

                tag[V[i]]=tag[now]+;

                if(!if_[V[i]]) que[tail++]=V[i],if_[V[i]]=true;

            }

        }

    }

    for(ll i=;i<=n;i++)

    {

        dis[i]=INF;

        if(!tag[i]) val[i]=INF;

        else if(tag[i]<=s) val[i]=Q;

        else val[i]=P;

    }

    val[]=,val[n]=;

}

void spfa2()

{

    ll h=,tail=;memset(if_,,sizeof(if_));

    dis[]=,que[tail++]=,if_[]=true;

    while(h<tail)

    {

        ll now=que[h++];if_[now]=false;

        for(ll i=head[now];i;i=E[i])

        {

            if(dis[now]+val[V[i]]<dis[V[i]])

            {

                dis[V[i]]=dis[now]+val[V[i]];

                if(!if_[V[i]]) que[tail++]=V[i],if_[V[i]]=true;

            }

        }

    }

    cout<<dis[n];

}

int main()

{

    in(n),in(m),in(k),in(s),in(P),in(Q),spfa1(),spfa2();

    return ;

}