题目描述

小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，表示一条无向边

一个整数表示最低花费

输入输出样例

13 21 1 11000 600071 23 72 45 88 92 53 44 79 1010 115 97 123 64 51 311 126 78 116 137 812 13

11000

说明

对于20%数据，N<=50

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

1 ≦ P ＜ Q ≦ 100000

 1 /**/ 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #include<algorithm> 7 using namespace std; 8 const long long inf=1000000000ll*1000000000ll+10ll; 9 const int mxn=500000;10 struct edge{11     int v,nxt;12 }e[mxn];13 int hd[mxn],cnt=0;14 void add_edge(int u,int v){15     e[++cnt].v=v;e[cnt].nxt=hd[u];hd[u]=cnt;16     return;17 }18 int n,m,k,s;19 long long P,Q;20 int kp[mxn];//被感染城市 21 bool da[mxn];//危险标记22 int head=0,tl=0;23 int q[mxn];24 long long dis[mxn];25 bool vis[mxn];26 bool ban[mxn];27 void dfs(int u)28 {29     if(dis[u]<=s)da[u]=1;30     if(dis[u]==s)return;31     for(int i=hd[u];i;i=e[i].nxt){32         int v=e[i].v;if(ban[v])continue;33         if(dis[v]>dis[u]+1){34             dis[v]=dis[u]+1;35             dfs(v);36         }37     }38     return;39 }40 41 bool inq[mxn];42 void SPFA(int x){43     for(int i=1;i<=n;i++)dis[i]=inf;44     head=1;tl=1;45     q[head]=x;46     dis[x]=0;47     inq[x]=1;48     while(head!=tl+1){49         int u=q[head];head=(head+1)%150000;50         for(int i=hd[u];i;i=e[i].nxt){51             int v=e[i].v;long long cst=(da[v])?Q:P;52             if(ban[v])continue;53             if(dis[v]>dis[u]+cst){54                 dis[v]=dis[u]+cst;55                 if(!inq[v]){56                     tl=(tl+1)%150000;57                     q[tl]=v;58                 }59             }60         }61         inq[u]=0;62     }63     return;64 }65 int main(){66     scanf("%d%d%d%d",&n,&m,&k,&s);67     int i,j;68     scanf("%lld%lld",&P,&Q);69     int u,v;70     for(i=1;i<=k;i++){71         scanf("%d",&kp[i]);72         ban[kp[i]]=1;73     }74     for(i=1;i<=m;i++){75         scanf("%d%d",&u,&v);76         add_edge(u,v);77         add_edge(v,u);78     }79     for(int i=1;i<=n;i++)dis[i]=inf;80     for(i=1;i<=k;i++){81         dis[kp[i]]=0;82         dfs(kp[i]);83     }84     SPFA(1);85     if(da[n])dis[n]-=Q;86     else dis[n]-=P;87     printf("%lld\n",dis[n]);88     return 0;89 }