71pts求助(WA #4,TLE#6)
查看原帖
71pts求助(WA #4,TLE#6)
1017629
ZSB00000楼主2024/8/3 11:03
#include<bits/stdc++.h>
#define int long long
using std::cin; 
using std::cout;
using std::endl;
int p, q;
int n, m, k, s;
bool _zhanling[(int)2e6+5];
bool dangerous[(int)2e6+5];
std::vector<std::pair<int,int>>point[(int)2e6+5];
std::priority_queue<int>queue;
int distance[(int)1e5+5];
std::queue<std::pair<int,int>>_queue;
void bfs()
{
	for(int i=1;i<=n;i++)
	{
		if(!dangerous[i]&&_zhanling[i])
		{
			_queue.push({i,0});
		}
	}
	while(!_queue.empty())
	{
		int x=_queue.front().first;
		int t=_queue.front().second;
		_queue.pop();
		if(t==s)
		{
			continue;
		}
		for(auto i: point[x])
		{
			
			if(!dangerous[i.first])
			{
				dangerous[i.first]=1;
				_queue.push({i.first,t+1});
			}
		}
	}
}
void dijkstra()
{
	for(int i=0;i<=1e5;i++)
	{
		distance[i]=INT_MAX;
	}
	distance[1]=0;
	queue.push(1);
	while(!queue.empty())
	{
		int _point=queue.top();
		queue.pop();
		for(auto it=point[_point].begin();it!=point[_point].end();it++)
		{
			if(_zhanling[it->first])
			{
				continue;
			}
			int value;
			if(dangerous[it->first])
			{
				value=q;
			}
			else
			{
				value=p;
			}
			if(it->first==n)
			{
				value=0;
			}
//			printf("From %d to %d need to cost %d\n",_point,it->first,value);
			if(distance[it->first]>distance[_point]+value)
			{
				distance[it->first]=distance[_point]+value;
				queue.push(it->first);
			}
		}
	}
}
signed main() {
	cin >> n >> m >> k >> s;
	cin >> p >> q;
	for(int i=1;i<=k;i++)
	{
		int c;
		cin>>c;
		_zhanling[c]=true;
	}
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		point[a].push_back({b,0});
		point[b].push_back({a,0});
	}
	bfs();
	dijkstra();
	cout<<distance[n]<<endl;
}
2024/8/3 11:03
加载中...