题解 P3393 【逃离僵尸岛】

2018-10-09 17:52:52


z

你没有发现两个字里的blog都不一样嘛 qwq

题目描述--->p3393 逃离僵尸岛

刷题有益于身心健康. 还有,谁说这是个简单题了 emm

分析

明显最短路的题。

但是需要注意的是有一些传染源,这些传染源会控制一些点.

我们需要 $Bfs$ 处理出这些点,标记它们是 $Safe$ 与否。

这里给出一些定义.

  • $Safe[i]==1$ 代表城市安全,居住价钱为 $P$
  • $Safe[i]==-1$ 表示城市为传染源,不可居住.
  • $Safe[i]==0$ 表示城市危险,居住价钱为 $Q$ .

这个时候预处理出来之后直接跑最短路就行.

但是需要注意的是,跑完最短路之后我们会在 $n$ 点居住。( $Dijkstra$ 吼啊

所以需要减去 $n$ 位置的价值。

注意需要判断 $n$ 点是否安全,而决定我们减去哪个费用

如果 $Wa$ 掉#4和#6的话需要将极大值赋的足够大.

还有 记得开 $long \ long $ !

代码

#include<cstdio>
#include<queue>
#include<cctype>
#define N 1000008
#define R register
#define int long long 
using namespace std;
inline void in(int &x)
{
    int f=1;x=0;char s=getchar();
    while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
    while(isdigit(s)){x=x*10+s-'0';s=getchar();}
    x*=f;
}
int n,m,k,S,c[N],head[N],tot,safe[N];
int p,Q,dis[N];
bool vis[N];
struct cod{int u,v;}edge[N<<4];
inline void add(int x,int y)
{
    edge[++tot].u=head[x];
    edge[tot].v=y;
    head[x]=tot;
}
struct coc{int u,dis;};
queue<coc>q1;//结构体版bfs
inline void bfs()
{
    while(!q1.empty())
    {
        int u=q1.front().u,dis=q1.front().dis;
        q1.pop();
        for(R int i=head[u];i;i=edge[i].u)
        {
            if(dis<S and safe[edge[i].v]==1)
            {
                safe[edge[i].v]=0;
                q1.push((coc){edge[i].v,dis+1});
            }
        }
    }
}
struct hop{
    int u,d;
    bool operator<(const hop&a)const
    {
        return d>a.d;
    }
};
inline void dij()//dijkstra
{
    for(R int i=1;i<=n;i++)dis[i]=21474836476666;
    priority_queue<hop>q;
    q.push((hop){1,0});dis[1]=0;
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
        if(vis[u])continue;
        vis[u]=true;
        for(R int i=head[u];i;i=edge[i].u)
        {
            if(safe[edge[i].v]==-1)continue;//如果-1不可居住
            if(safe[edge[i].v]==0)
                if(dis[edge[i].v]>dis[u]+Q)
                {
                    dis[edge[i].v]=dis[u]+Q;
                    q.push((hop){edge[i].v,dis[edge[i].v]});
                }
            if(safe[edge[i].v]==1)
                if(dis[edge[i].v]>dis[u]+p)
                {
                    dis[edge[i].v]=dis[u]+p;
                    q.push((hop){edge[i].v,dis[edge[i].v]});
                }
        }
    }
}
signed main()
{
    in(n),in(m),in(k),in(S);
    in(p),in(Q);
    for(R int i=1;i<=n;i++)safe[i]=1;//刚开始都是安全的.
    for(R int i=1;i<=k;i++)
    {
        in(c[i]),safe[c[i]]=-1;//标记为不安全
        q1.push((coc){c[i],0});
    }
    for(R int i=1,x,y;i<=m;i++)
    {
        in(x),in(y);
        add(x,y);add(y,x);
    }
    bfs();dij();
    if(safe[n]==0)dis[n]-=Q;
    else dis[n]-=p;//判断是n是哪种城市
    printf("%lld",dis[n]);
    return 0;
}