题目描述
小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
Solution：
本题最短路板子+小思维。
首先就是建立虚点$0$连向被控制的点，令边长为$1$，广搜一遍，求出各点到虚点的距离，然后判断没被控制的各点距离是否不大于$s+1$，就能处理出所有危险的点，标记一下。
然后就是跑一遍spfa，每次判断连向的点是否被标记，然后选择边权差分约束。
但是这样算会算上到了$n$点的花费，而题意到了$n$点就不需要花费了，于是最后输出的答案还得减去多加的到$n$点的花费，然后就OK了（注意答案会爆int）。
代码：
#include#define il inline#define ll long long#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)using namespace std;const ll N=500005,inf=23333333333;ll n,m,k,s,p,q;ll h[N],net[N],dis[N],cnt,to[N];bool vis[N],ct[N],bj[N];il ll gi(){ ll a=0;char x=getchar();bool f=0; while((x<'0'||x>'9')&&x!='-')x=getchar(); if(x=='-')x=getchar(),f=1; while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar(); return f?-a:a;}il void add(int u,int v){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt;}il void pre(){ queue q; For(i,1,n) dis[i]=inf; q.push(0); while(!q.empty()){ int u=q.front();q.pop();vis[u]=0; for(int i=h[u];i;i=net[i]) if(dis[to[i]]>dis[u]+1){ dis[to[i]]=dis[u]+1; if(!vis[to[i]])q.push(to[i]),vis[to[i]]=1; } } For(i,1,n) if(dis[i]<=s&&!ct[i]) bj[i]=1;}il void spfa(){ queue Q; For(i,1,n) dis[i]=inf; dis[1]=0; Q.push(1); while(!Q.empty()){ int u=Q.front();Q.pop();vis[u]=0; for(int i=h[u];i;i=net[i]) if(!ct[to[i]]){ if(bj[to[i]]){ if(dis[to[i]]>dis[u]+q){ dis[to[i]]=dis[u]+q; if(!vis[to[i]])Q.push(to[i]),vis[to[i]]=1; } } else { if(dis[to[i]]>dis[u]+p){ dis[to[i]]=dis[u]+p; if(!vis[to[i]])Q.push(to[i]),vis[to[i]]=1; } } } } if(bj[n]==1)cout<