luogu P3393 逃離僵屍島

analysis

關鍵是解決這個問題:

給你幾個點，其他的點離這些給出的點的最近距離是多少

這個很簡單:

我們可以自己給出一個點，然後向每個被标記的點連一條單向邊，這樣就隻需要進行一次 dijkstra 就可以了。

code

#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define clean(arry,num) memset(arry,num,sizeof(arry))
#define anti_loop(i,start,end) for(register int i=start;i>=end;--i)
#define ll long long
#define isdegit(r) ((r>='0'&&r<='9'))
template<typename T>void read(T &x){
	x=0;char r=getchar();T neg=1;
	while(!isdegit(r)){if(r==45)neg=-1;r=getchar();}
	while(isdegit(r)){x=(x<<1)+(x<<3)+r-48;r=getchar();}
	x*=neg;
}
int n,m,k,s,p,q;
const int maxn=100000+10;
const int maxm=200000+10;
const int maxs=100000+10;
int C[maxn];
struct node{
	int e;
	int nxt;
}edge[maxm<<2];
int head[maxn];
int cnt=0;
inline void addl(int u,int v){
	edge[cnt].e=v;
	edge[cnt].nxt=head[u];
	head[u]=cnt++;
}
struct point{
	int pos;
	ll dis;
	point(int pos=0,ll dis=0):pos(pos),dis(dis){}
	friend bool operator<(point a,point b){
		return a.dis>b.dis;
	}
};
priority_queue<point>Q;
ll dis[maxn];
bool safe[maxn];
bool zb[maxn];
inline void dijkstra(int S,bool num){
	clean(dis,0x3f);
	dis[S]=0;
	Q.push(point(S,0));
	while(Q.empty()==false){
		int f=Q.top().pos;
		Q.pop();
		for(int i=head[f];i!=-1;i=edge[i].nxt){
			int v=edge[i].e;
			if(num==1&&zb[v]==true)continue;
			int w=(safe[v]?p:q);
			if((v!=n||num==0)&&dis[v]>dis[f]+(num==1?w:1)){
				dis[v]=dis[f]+(num==1?w:(f==0?0:1));
				Q.push(point(v,dis[v]));
			}
			else if(v==n){
				dis[v]=min(dis[v],dis[f]);
			}
		}
	}
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("datain.txt","r",stdin);
	#endif
	clean(head,-1);
	clean(zb,false);
	read(n),read(m),read(k),read(s);
	read(p),read(q);
	loop(i,1,n)safe[i]=true;
	loop(i,1,k)read(C[i]),zb[C[i]]=true;
	loop(i,1,m){
		int ai,bi;read(ai),read(bi);
		addl(ai,bi),addl(bi,ai);
	}
	loop(i,1,k)addl(0,C[i]),dis[C[i]]=0;
	dijkstra(0,0);
	loop(i,1,n){
		if(dis[i]<=s)safe[i]=false;
	}
	dijkstra(1,1);
	printf("%lld\n",dis[n]);
	return 0;
}