首页 > 代码库 > AC日记——逃离僵尸岛 洛谷 P3393

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 longll 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=0;    while(Cget>9||Cget<0) Cget=getchar();    while(Cget>=0&&Cget<=9)    {        now=now*10+Cget-0;        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=0,tail=0,pos,u,v;    memset(if_,0,sizeof(if_));    for(int i=1;i<=n;i++) tag[i]=INF;    for(ll i=1;i<=k;i++) in(pos),que[tail++]=pos,tag[pos]=0,if_[pos]=true;    for(ll i=1;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]+1<tag[V[i]])            {                tag[V[i]]=tag[now]+1;                if(!if_[V[i]]) que[tail++]=V[i],if_[V[i]]=true;            }        }    }    for(ll i=1;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[1]=0,val[n]=0;}void spfa2(){    ll h=0,tail=0;memset(if_,0,sizeof(if_));    dis[1]=0,que[tail++]=1,if_[1]=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 0;}

 

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