28pts求助(WA+MLE)
查看原帖
28pts求助(WA+MLE)
1019894
xy_baifengxiang楼主2025/1/25 19:31
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ri register ll
struct POINT{
	ll pos,val;
	inline bool operator <(const POINT x)const{
		return val>x.val;
	}
};
vector<ll>point[100010];
ll n,m,k,s,p,q,shortest[100010];
bool pd[100010],pdpd[100010],jl[100010];
priority_queue<POINT>pque;
queue<pair<ll,ll>>bque;
inline void bfs() {
	if(bque.empty())return;
	auto a=bque.front();
	bque.pop();
	pd[a.first]=1;
	if(a.second==k) {
		bfs();
		return;
	}
	for(auto z:point[a.first]){
		bque.push(make_pair(z,a.second+1ll));
	}
	bfs();
}
inline POINT make_point(ll pos,ll val){
	POINT x;
	x.val=val;
	x.pos=pos;
	return x;
}
inline void dijkstra(){
	shortest[1]=0;
	pque.push(make_point(1ll,0ll));
	while(!pque.empty()){
		auto a=pque.top();
		pque.pop();
		if(a.val!=shortest[a.pos]||jl[a.pos])continue;
		jl[a.pos]=1;
		for(auto z:point[a.pos]){
			if(z==1ll||pdpd[z])continue;
			ll v;
			if(z==n)v=0ll;
			else if(pd[z])v=q;
			else v=p;
			if(shortest[z]>v+a.val){
				shortest[z]=v+a.val;
				pque.push(make_point(z,shortest[z]));
			}
		}
	}
}
signed main(int argv,char**argc) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k>>s>>p>>q;
	for(ri z=1; z<=n; z++) {
		shortest[z]=LLONG_MAX;
	}
	for(ri z=1; z<=k; z++) {
		ll c;
		cin>>c;
		pdpd[c]=1;
		bque.push(make_pair(c,0));
	}
	for(ri z=1; z<=m; z++) {
		ll a,b;
		cin>>a>>b;
		point[a].push_back(b);
		point[b].push_back(a);
	}
	bfs();
	dijkstra();
	cout<<shortest[n];
	return 0;
}

#1 #2 AC
#3 #4 WA
#5 #6 #7 MLE

2025/1/25 19:31
加载中...