では、ゲームを始めましょう
GO FOR IT !

K个城市已经被僵尸控制了,如果贸然闯入就会被感染TAT...所以不能进入!!!

首先,注意几个细节!

  1. 如上方大字,不能进入被控制的城市(qwq)

  2. dis距离开long long,最大值也要开的足够大!(数据超int了)

  3. 将点值附在边权上的同志们,记得最后到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;
}
总访问量 访问人数