Submission #294549

#	Time	Username	Problem	Language	Result	Execution time	Memory
294549		nandonathaniel	Relay Marathon (NOI20_relaymarathon)	C++14	100 / 100	2503 ms	127784 KiB

RelayMarathon

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
const int MAXN=1e5+5,INF=1e9;

vector<pii> adj[MAXN];
int head[MAXN],dist[MAXN],n;
bool special[MAXN],skip[MAXN];

piii MinimumPairSpecialDistance(){
	priority_queue<pii,vector<pii>,greater<pii>> PQ;
	for(int i=1;i<=n;i++)dist[i]=INF;
	for(int i=1;i<=n;i++){
		if(!special[i] || skip[i])continue;
		dist[i]=0;
		head[i]=i;
		PQ.push({dist[i],i});
	}
	while(!PQ.empty()){
		pii now=PQ.top();
		PQ.pop();
		if(dist[now.second]<now.first)continue;
		for(auto nxt : adj[now.second]){
			if(!skip[nxt.first] && dist[now.second]+nxt.second<dist[nxt.first]){
				dist[nxt.first]=dist[now.second]+nxt.second;
				head[nxt.first]=head[now.second];
				PQ.push({dist[nxt.first],nxt.first});
			}
		}
	}
	int val=INF;
	pii ret;
	for(int i=1;i<=n;i++){
		for(auto j : adj[i]){
			if(head[i]==head[j.first] || skip[head[i]] || skip[head[j.first]])continue;
			if(dist[i]+j.second+dist[j.first]<val){
				val=dist[i]+j.second+dist[j.first];
				ret={head[i],head[j.first]};
			}
		}
	}
	return {val,ret};
}

int kasusdua(int a,int b){
	priority_queue<pii,vector<pii>,greater<pii>> PQ;
	for(int i=1;i<=n;i++)dist[i]=INF;
	dist[a]=0;
	PQ.push({dist[a],a});
	while(!PQ.empty()){
		pii now=PQ.top();
		PQ.pop();
		if(dist[now.second]<now.first)continue;
		for(auto nxt : adj[now.second]){
			if(dist[now.second]+nxt.second<dist[nxt.first]){
				dist[nxt.first]=dist[now.second]+nxt.second;
				PQ.push({dist[nxt.first],nxt.first});
			}
		}
	}
	vector<pii> jaraka;
	for(int i=1;i<=n;i++){
		if(i==a || i==b || !special[i])continue;
		jaraka.push_back({dist[i],i});
	}
	sort(jaraka.begin(),jaraka.end());
	for(int i=1;i<=n;i++)dist[i]=INF;
	dist[b]=0;
	PQ.push({dist[b],b});
	while(!PQ.empty()){
		pii now=PQ.top();
		PQ.pop();
		if(dist[now.second]<now.first)continue;
		for(auto nxt : adj[now.second]){
			if(dist[now.second]+nxt.second<dist[nxt.first]){
				dist[nxt.first]=dist[now.second]+nxt.second;
				PQ.push({dist[nxt.first],nxt.first});
			}
		}
	}
	vector<pii> jarakb;
	for(int i=1;i<=n;i++){
		if(i==a || i==b || !special[i])continue;
		jarakb.push_back({dist[i],i});
	}
	sort(jarakb.begin(),jarakb.end());
	if(jaraka[0].second==jarakb[0].second)return min(jaraka[0].first+jarakb[1].first,jaraka[1].first+jarakb[0].first);
	else return jaraka[0].first+jarakb[0].first;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int m,k,u,v,w;
	cin >> n >> m >> k;
	for(int i=1;i<=m;i++){
		cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	for(int i=1;i<=k;i++){
		cin >> u;
		special[u]=true;
	}
	piii temp=MinimumPairSpecialDistance();
	int kasussatu=temp.first,a=temp.second.first,b=temp.second.second;
	skip[a]=true;skip[b]=true;
	kasussatu+=MinimumPairSpecialDistance().first;
	int ans=kasussatu;
	ans=min(ans,kasusdua(a,b));
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 25 / 25
• Subtask 4: 58 / 58