萌新:逃离僵尸岛
查看原帖
萌新:逃离僵尸岛
658786
STUDENT00楼主2022/8/25 21:21

用动态数组来存边,SPFA最短路,求大佬!

#include<bits/stdc++.h>
using namespace std;
int n,m,k,s,p,q,num[100010],x,y,dis[100010];
bool c[100010],d[100010],vis[100010];
struct node{
	int q,s;
};
vector<node> a[100010];
queue<int> qt;
void SPFA(int u){
	for(int i=0;i<=n;i++){
		dis[i]=1e7;
		vis[i]=0;
	}
	dis[u]=0;
	vis[u]=1;
	qt.push(u);
	while(!qt.empty()){
		int now=qt.front();
		vis[now]=0;
		for(int i=0;i<num[now];i++){
			if(dis[a[now][i].q]>dis[now]+a[now][i].s){
				dis[a[now][i].q]=dis[now]+a[now][i].s;
				if(!vis[a[now][i].q]){
					vis[a[now][i].q]=1;
					qt.push(a[now][i].q);
				}
			}
		}
		qt.pop();
	}
}
int main(){
	scanf("%d%d%d%d%d%d",&n,&m,&k,&s,&p,&q);
	while(k--){
		scanf("%d",&x);
		c[x]=1;
	}
	while(m--){
		scanf("%d%d",&x,&y);
		if(c[x]&&c[y]) continue;
		if(c[x]) x=0;
		if(c[y]) y=0;
		a[x].push_back({y,1});
		a[y].push_back({x,1});
		num[x]++;
		num[y]++;
	}
	SPFA(0);
	for(int i=1;i<=n;i++){
		if(dis[i]<=s) d[i]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<num[i];j++){
			if(a[i][j].q==n) a[i][j].s=0;
			else if(c[i]||c[a[i][j].q]) a[i][j].s=1e7;
			else if(d[i]||d[a[i][j].q]) a[i][j].s=q;
			else a[i][j].s=p;
		}
	}
	SPFA(1);
	printf("%d",dis[n]);
	return 0;
}
2022/8/25 21:21
加载中...