求助,56分WA(悬赏关注)
查看原帖
求助,56分WA(悬赏关注)
800499
suzhikz楼主2023/7/9 14:09
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<string.h>
using namespace std;
long long n,m,k,s,p,qq,u,v;
long long a[200005],b[200005];
vector<long long> g[200005];
void bfs(long long x){
	long long deep[200005];
	queue<long long>q;
	q.push(x);
	a[x]=-1;
	deep[x]=1;
	while(!q.empty()){
		long long y=q.front();
		q.pop();
		if(deep[y]>=s+1)break;
		for(long long i=0;i<g[y].size();i++){
			if(!deep[g[y][i]]){
				deep[g[y][i]]=deep[y]+1;
				a[g[y][i]]=qq;
				q.push(g[y][i]);
			}
		}
		
	} 
	//for(long long i=1;i<=n;i++)cout<<deep[i]<<' ';
	return;
}
long long dis[200005];
bool vis[200005];
struct node{
	long long id,cost;
	bool operator< (const node &x)const{
		return cost>x.cost;
	}
};
priority_queue<node> q;
void dijkstra(){
	for( int i=1;i<=n;i++)dis[i]=21474836476666;
	q.push((node){1,0});
	dis[1]=0;
	while(!q.empty()){
		long long x=q.top().id;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(long long i=0;i<g[x].size();i++){
			if(a[g[x][i]]!=-1&&dis[g[x][i]]>dis[x]+a[g[x][i]]){
				dis[g[x][i]]=dis[x]+a[g[x][i]];
				q.push((node){g[x][i],dis[g[x][i]]});
			}
		}
	} 
	return;
}
signed main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	//cout.tie(0);
	cin>>n>>m>>k>>s>>p>>qq;
	for(long long i=1;i<=n;i++)a[i]=p;
	for(long long i=1;i<=k;i++)cin>>b[i];
	for(long long i=1;i<=m;i++){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(long long i=1;i<=k;i++){
		bfs(b[i]);
	}
	//for(long long i=1;i<=n;i++)cout<<a[i]<<' ';
	//cout<<endl;
	dijkstra();
	cout<<dis[n]-a[n];
	return 0;
}

2023/7/9 14:09
加载中...