Submission #873516

#	Time	Username	Problem	Language	Result	Execution time	Memory
873516		dsyz	Relay Marathon (NOI20_relaymarathon)	C++17	100 / 100	1663 ms	285320 KiB

RelayMarathon

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (100005)
ll dist[MAXN], distA[MAXN], distB[MAXN];
ll source[MAXN];
vector<pair<ll,ll> > v[MAXN];
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,M,K;
	cin>>N>>M>>K;
	vector<pair<ll,pair<ll,ll> > > edges;
	for(ll i = 0;i < M;i++){
		ll a,b,c;
		cin>>a>>b>>c;
		a--;
		b--;
		v[a].push_back({c,b});
		v[b].push_back({c,a});
		edges.push_back({c,{a,b}});
	}
	priority_queue<pair<ll,pair<ll,ll> >,vector<pair<ll,pair<ll,ll> > >,greater<pair<ll,pair<ll,ll> > > > pq;
	ll special[K];
	memset(dist,-1,sizeof(dist));
	memset(source,-1,sizeof(source));
	for(ll i = 0;i < K;i++){
		cin>>special[i];
		special[i]--;
		pq.push({0,{special[i],special[i]}}); //d, cur node, source
		dist[special[i]] = 0;
		source[special[i]] = special[i];
	}
	while(!pq.empty()){
		ll d = pq.top().first;
		ll x = pq.top().second.first;
		ll Source = pq.top().second.second;
		pq.pop();
		if(d != dist[x]){
			continue;
		}
		for(auto u : v[x]){
			if(dist[u.second] == -1 || d + u.first < dist[u.second]){
				pq.push({d + u.first,{u.second,Source}});
				dist[u.second] = d + u.first;
				source[u.second] = Source;
			}
		}
	}
	ll A = -1, B = -1, minimum = 1e18;
	for(auto u : edges){
		ll a = u.second.first;
		ll b = u.second.second;
		ll c = u.first;
		if(dist[a] == -1 || dist[b] == -1 || source[a] == source[b]){
			continue;
		}
		if(dist[a] + c + dist[b] <= minimum){
			minimum = dist[a] + c + dist[b];
			A = source[a];
			B = source[b];
		}
	}
	
	ll sum = 1e18;
	//Case 1: First Pair (A, B) fixed, Second pair (C, D) unknown
	memset(dist,-1,sizeof(dist));
	memset(source,-1,sizeof(source));
	for(ll i = 0;i < K;i++){
		if(special[i] != A && special[i] != B){
			//cout<<"SOURCE: "<<special[i]<<'\n';
			pq.push({0,{special[i],special[i]}}); //d, cur node, source
			dist[special[i]] = 0;
			source[special[i]] = special[i];
		}
	}
	while(!pq.empty()){
		ll d = pq.top().first;
		ll x = pq.top().second.first;
		ll Source = pq.top().second.second;
		pq.pop();
		if(x == A || x == B) continue;
		if(d != dist[x]){
			continue;
		}
		for(auto u : v[x]){
			if(u.second == A || u.second == B) continue;
			if(dist[u.second] == -1 || d + u.first < dist[u.second]){
				pq.push({d + u.first,{u.second,Source}});
				dist[u.second] = d + u.first;
				source[u.second] = Source;
			}
		}
	}
	ll C = -1, D = -1, minimum2 = 1e18;
	for(auto u : edges){
		ll a = u.second.first;
		ll b = u.second.second;
		ll c = u.first;
		if(dist[a] == -1 || dist[b] == -1 || source[a] == source[b]){
			continue;
		}
		if(dist[a] + c + dist[b] <= minimum2){
			minimum2 = dist[a] + c + dist[b];
			C = source[a];
			D = source[b];
		}
	}
	sum = min(sum,minimum + minimum2);
	//cout<<"Case 1 SUM: "<<minimum + minimum2<<" "<<A<<" with "<<B<<" ,  "<<C<<" with "<<D<<'\n';
	
	//Case 2: Half of both pairs are known (A, C) and (B, D)
	memset(distA,-1,sizeof(distA));
	pq.push({0,{A,A}}); //d, cur node, source
	distA[A] = 0;
	source[A] = A;
	while(!pq.empty()){ //dikjstra from A
		ll d = pq.top().first;
		ll x = pq.top().second.first;
		ll Source = pq.top().second.second;
		pq.pop();
		if(d != distA[x]){
			continue;
		}
		for(auto u : v[x]){
			if(distA[u.second] == -1 || d + u.first < distA[u.second]){
				pq.push({d + u.first,{u.second,Source}});
				distA[u.second] = d + u.first;
				source[u.second] = Source;
			}
		}
	}
	pair<ll,ll> C1 = {-1,1e18}, C2 = {-1,1e18}; //first-best choice for C, second-best choice for C
	for(ll i = 0;i < K;i++){
		ll x = special[i];
		if(distA[x] == -1 || x == A || x == B) continue;
		if(distA[x] <= C1.second){
			C2 = C1;
			C1 = {x,distA[x]};
		}else if(distA[x] <= C2.second){
			C2 = {x,distA[x]};
		}
	}
	
	memset(distB,-1,sizeof(distB));
	pq.push({0,{B,B}}); //d, cur node, source
	distB[B] = 0;
	source[B] = B;
	while(!pq.empty()){ //dikjstra from B
		ll d = pq.top().first;
		ll x = pq.top().second.first;
		ll Source = pq.top().second.second;
		pq.pop();
		if(d != distB[x]){
			continue;
		}
		for(auto u : v[x]){
			if(distB[u.second] == -1 || d + u.first < distB[u.second]){
				pq.push({d + u.first,{u.second,Source}});
				distB[u.second] = d + u.first;
				source[u.second] = Source;
			}
		}
	}
	
	for(ll i = 0;i < K;i++){
		ll D = special[i];
		if(D == A || D == B || C1.first == -1 || distB[D] == -1) continue;
		if(D == C1.first){
			if(C2.first == -1) continue;
			sum = min(sum,C2.second + distB[D]);
			//cout<<"Case 2 SUM: "<<C2.second + distB[D]<<" "<<A<<" with "<<C2.first<<" ,  "<<B<<" with "<<D<<'\n';
		}else{
			sum = min(sum,C1.second + distB[D]);
			//cout<<"Case 2 SUM: "<<C1.second + distB[D]<<" "<<A<<" with "<<C1.first<<" ,  "<<B<<" with "<<D<<'\n';
		}
	}
	cout<<sum<<'\n';
}

Compilation message (stderr)

RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:94:5: warning: variable 'C' set but not used [-Wunused-but-set-variable]
   94 |  ll C = -1, D = -1, minimum2 = 1e18;
      |     ^
RelayMarathon.cpp:94:13: warning: variable 'D' set but not used [-Wunused-but-set-variable]
   94 |  ll C = -1, D = -1, minimum2 = 1e18;
      |             ^

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