28pts求调(玄关)WA了5个点
查看原帖
28pts求调(玄关)WA了5个点
1144893
Kenneth1楼主2024/11/30 19:15
#include <bits/stdc++.h>
using namespace std;
struct node{
	long long end;
	long long len;
};
vector <long long> b[500010];
long long n,m,s,k,p,q1,jiang[500010];
queue <long long> q;
long long vis[500010],d[500010],a[500010];
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>m>>s>>k;
	cin>>p>>q1;
	for(long long i=0;i<=n;i++){
		d[i]=1e15;
		a[i]=p;
	}
	for(long long i=1;i<=k;i++){
		cin>>jiang[i];
		a[jiang[i]]=1e15;
		b[0].push_back(jiang[i]);
		b[jiang[i]].push_back(0);
	}
	for(long long i=1;i<=m;i++){
		long long x,y;
		cin>>x>>y;
		b[x].push_back(y);
		b[y].push_back(x);
	}
	vis[0]=1;
	d[0]=0;
	q.push(0);
	while(!q.empty()){
		long long u=q.front();
		q.pop();
		vis[u]=0;
		for(long long i=0;i<b[u].size();i++){
			long long w=1,v=b[u][i];
			if(d[u]+w<d[v]){
				d[v]=d[u]+w;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		} 
	}
	for(long long i=1;i<=n;i++){
		if(d[i]<=s+1){
			if(a[i]!=1e15)
				a[i]=q1;
			else
				b[i].erase(b[i].begin());
		}
	}
	b[0].clear();
	for(long long i=0;i<=n;i++){
		d[i]=1e15;
		vis[i]=0;
	}
	vis[1]=1;
	d[1]=0;
	q.push(1);
	while(!q.empty()){
		long long u=q.front();
		q.pop();
		vis[u]=0;
		for(long long i=0;i<b[u].size();i++){
			long long w,v=b[u][i];
			w=a[v];
			if(d[u]+w<d[v]){
				d[v]=d[u]+w;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		} 
	}
	cout<<d[n]-a[n];
	return 0;
}

2024/11/30 19:15
加载中...