社区讨论

86pts求条,WA on #3

P3393逃离僵尸岛参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mkkxm5dr
此快照首次捕获于
2026/01/19 16:57
2 个月前
此快照最后确认于
2026/01/23 12:45
2 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,k,s,p,q;
int flag[N];
int dist[N],vis[N];
queue<pair<int,int>> qq;
vector<int> pic[N];
void dk();
signed main(){
	cin>>n>>m>>k>>s>>p>>q;
	for(int i=1;i<=k;i++){
		int x;
		cin>>x;
		qq.push(make_pair(x,0));
	}
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		pic[u].push_back(v);
		pic[v].push_back(u);
	}
	while(!qq.empty()){
		int u=qq.front().first;
		int d=qq.front().second;
		if(d==0) flag[u]=2;
		else flag[u]=1;
		qq.pop();
		int len=pic[u].size();
		for(int i=0;i<len;i++){
			int v=pic[u][i];
			if(!flag[v]&&d+1<=s) qq.push(make_pair(v,d+1));
		}
	}
	dk();
	cout<<dist[n];
}
void dk(){
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	memset(dist,0x3f3f,sizeof(dist));
	dist[1]=0;
	pq.push(make_pair(dist[1],1));
	while(!pq.empty()){
		int u=pq.top().second;
		int d=pq.top().first;pq.pop();
		if(vis[u]) continue;
		vis[u]=1;
		int len=pic[u].size();
		for(int i=0;i<len;i++){
			int v=pic[u][i];
			int w;
			if(flag[v]==2) continue;
			else if(v==n) w=0;
			else if(flag[v]==1) w=q;
			else w=p;
			if(d+w<dist[v]){
				dist[v]=d+w;
				pq.push(make_pair(dist[v],v));
			}
		}
	}
}

回复

1 条回复,欢迎继续交流。

正在加载回复...