K个城市已经被僵尸控制了,如果贸然闯入就会被感染TAT...所以不能进入!!!
首先,注意几个细节!
-
如上方大字,不能进入被控制的城市(qwq)
-
dis距离开long long,最大值也要开的足够大!(数据超int了)
-
将点值附在边权上的同志们,记得最后到n点减去,然后n点可以是危险城市!
讲下做法:
大部分dalao们都是bfs或者将k点全部看做0点来做的
本蒟蒻就直接更新k次,把每个被控制城市附近的危险城市标记
然而直接来肯定会T的飞起qwq
所以要剪枝
见代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define res register int
const int MAXN=100000+100;
const ll INF=0x3f3f3f3f3f3f3f3f;//dis最大值要足够大才行
int n,m,k,s,P,Q,cnt=1,head[MAXN],vis[MAXN],ban[MAXN];
ll dis[MAXN];//dis开long long
struct EDGE{int to,next;}edge[MAXN<<2];
queue<int> bad;
inline void E_add(int u,int v){edge[cnt]=(EDGE){v,head[u]};head[u]=cnt++;}
void spfa_flag(int S){
queue<int> q;
for(res i=1;i<=n;++i) dis[i]=INF;
memset(vis,0,sizeof(vis));
q.push(S),dis[S]=0;
while(q.size()){
int x=q.front();q.pop();
vis[x]=0;
for(res i=head[x];i;i=edge[i].next){
int y=edge[i].to,z=1;
if(ban[y]!=2&&dis[y]>dis[x]+z){
//此处注意!当y点被标记为2,说明y点是另一个被控制的城市,
//我们就不用管它,跳过
dis[y]=dis[x]+1;
if(dis[y]<=s) ban[y]=1;
//当y点到x点(一个被控城市)的距离小于s,
//就标记为1,表示危险城市
if(!vis[y]&&dis[y]<s) vis[y]=1,q.push(y);
//此处注意!
//当y点到x点距离小于s才把y点加入队列,
//因为如果y点到x点距离大于或等于s时,说明y点在x的危险范围的边缘,
//再用y点更新最短路就没有意义,因为肯定没有距离小于s的点在y点外面
}
}
}
}
void spfa(){
queue<int> q;
for(res i=1;i<=n;++i) dis[i]=INF;
memset(vis,0,sizeof(vis));
q.push(1),dis[1]=0;
while(q.size()){
int x=q.front();q.pop();
vis[x]=0;
for(res i=head[x];i;i=edge[i].next){
int y=edge[i].to,z=(ban[y]?Q:P);
if(ban[y]!=2&&dis[y]>dis[x]+z){//此处注意!
//当y为被控城市时不能走!!!
//(qwq我眼瞎,错了近十次才看清题目)
dis[y]=dis[x]+z;
if(!vis[y]) vis[y]=1,q.push(y);
}
}
}
}
int main(){
scanf("%d%d%d%d%d%d",&n,&m,&k,&s,&P,&Q);
for(res i=1;i<=k;++i){
int x; scanf("%d",&x);ban[x]=2,bad.push(x);
}//被控制城市标记为2,然后存bad队列中
for(res i=1;i<=m;++i){
int x,y; scanf("%d %d",&x,&y);
E_add(x,y),E_add(y,x);
}
while(bad.size()){
spfa_flag(bad.front());bad.pop();
}
spfa();
if(ban[n]) dis[n]-=Q;//在n点减去花费,以为n点不收钱
else dis[n]-=P;//还有一件事,n点可以为危险城市!!
printf("%lld",dis[n]);
return 0;
}