洛谷 P3393 逃离僵尸岛

题目描述

小a住的国家被僵尸侵略了！小a打算逃离到该国唯一的国际空港逃出这个国家。

该国有N个城市，城市之间有道路相连。一共有M条双向道路。保证没有自环和重边。

K个城市已经被僵尸控制了，如果贸然闯入就会被感染TAT...所以不能进入。由其中任意城市经过不超过S条道路就可以到达的别的城市，就是危险城市。换句话说只要某个没有被占城市到某个被占城市不超过s距离，就是危险。

小a住在1号城市，国际空港在N号城市，这两座城市没有被侵略。小a走每一段道路（从一个城市直接到达另外一个城市）得花一整个白天，所以晚上要住旅店。安全的的城市旅馆比较便宜要P元，而被危险的城市，旅馆要进行安保措施，所以会变贵，为Q元。所有危险的城市的住宿价格一样，安全的城市也是。在1号城市和N城市，不需要住店。

小a比较抠门，所以他希望知道从1号城市到N号城市所需要的最小花费。

输入数据保证存在路径，可以成功逃离。输入数据保证他可以逃离成功。

输入输出格式

输入格式：

第一行4个整数(N,M,K,S)

第二行2个整数(P,Q)

接下来K行，ci，表示僵尸侵占的城市

接下来M行，ai,bi，表示一条无向边

输出格式：

一个整数表示最低花费

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

对于20%数据，N<=50

对于100%数据，2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2, 0 ≦ S ≦ 100000

1 ≦ P ＜ Q ≦ 100000

思路：题目比较简单，但因为细节，挂的比较惨。。。

一个一个压进栈和全部一起压入，第一种方法可能会漏解。

/*
关键在于在尽量短的时间内判断一个城市是
安全城市还是被危险城市。
最后跑一个最短路。
数组边开两倍。 

首先 开long long  
*/
#include<queue> 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100010
using namespace std;
int n,m,k,s,p,q,tot;
int c[MAXN],vis[MAXN];
long long cost[MAXN],dis[MAXN];
struct nond{ long long dis;int id; };
int to[MAXN*4],net[MAXN*4],head[MAXN];
queue<nond>qu;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool operator < (const nond &a,const nond &b){
    return a.dis>b.dis;
}
void add(int u,int v){
    to[++tot]=v;net[tot]=head[u];head[u]=tot;
}
void work(){
    while(!qu.empty()){
        nond tmp=qu.front();
        qu.pop();
        if(tmp.dis==s)    continue;
        for(int i=head[tmp.id];i;i=net[i])//wa点 
            if(!vis[to[i]]){
                vis[to[i]]=1;cost[to[i]]=q;
                qu.push((nond){tmp.dis+1,to[i]});
            }
    }
}
void dijkstra(int be){
    priority_queue<nond>que;
    for(int i=1;i<=n;i++)    dis[i]=21474836476666;//wa点 
    dis[be]=0;que.push((nond){0,be});
    while(!que.empty()){
        nond now=que.top();
        que.pop();
        if(dis[now.id]!=now.dis)    continue;
        for(int i=head[now.id];i;i=net[i])
            if(dis[to[i]]>dis[now.id]+cost[to[i]]){
                dis[to[i]]=dis[now.id]+cost[to[i]];
                que.push((nond){dis[to[i]],to[i]});
            }
    }
}
int main(){
    n=read();m=read();k=read();s=read();
    p=read();q=read();
    for(int i=1;i<=k;i++){
        c[i]=read();vis[c[i]]=1; 
        cost[c[i]]=21474836476666;//wa点 
        qu.push((nond){0,c[i]});
    }    
    for(int i=1;i<=m;i++){
        int u=read();
        int v=read();
        add(u,v);add(v,u);
    }
    work();
    for(int i=1;i<=n;i++)
        if(!cost[i])    cost[i]=p;
    cost[1]=cost[n]=0;
    dijkstra(1);
    printf("%lld",dis[n]);
}