Submission #1303058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303058		samarthkulkarni	Relay Marathon (NOI20_relaymarathon)	C++20	5 / 100	6107 ms	512792 KiB

RelayMarathon

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pb push_back
#define pr pair<ll, ll>
#define ff first
#define ss second

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}


const int N = 1e5+10;
const long long inf = 1e18;
vector<pr> adj[N];
ll dist[2][N];
int st[2][N];


void solution() {
	memset(st, -1, sizeof(st));
	fill(dist[0], dist[0]+N, inf);
	fill(dist[1], dist[1]+N, inf);

	ll n, m, k; 
	cin >> n >> m >> k;

	while (m--) {
		ll a, b, w;
		cin >> a >> b >> w;
		adj[a].pb({b, w});
		adj[b].pb({a, w});
	}


	vi v(k);
	for (ll &z : v) cin >> z;



	auto cal = [&](int a, int from, ll d) {
		if (dist[0][a] > d) {
			swap(dist[0][a], dist[1][a]);
			swap(st[0][a], st[1][a]);

			dist[0][a] = d;
			st[0][a] = from;
		} else if (dist[1][a] > d) {
			dist[1][a] = d;
			st[1][a] = from;
		}
	};


	priority_queue<array<ll, 3>> q;
	// {dist, curr, from}


	for (auto a : v) {
		for (auto [b, w] : adj[a]) {
			q.push({-w, b, a});
		}
	}

	while (!q.empty()) {
		auto [d, a, f] = q.top(); q.pop();

		if (st[1][a] != -1 || f == a ||
			st[0][a] == f || st[1][a] == f) continue;

		cal(a, f, -d);

		for (auto [b, w] : adj[a]) {
			q.push({d-w, b, f});
		}
	}


	auto era = [&](vi &t) {
		sort(all(t));
		t.erase(unique(all(t)), t.end());
	};


	vector<array<ll, 3>> avl;

	for (auto a : v) {
		if (st[0][a] != -1)
			avl.pb({dist[0][a], a, st[0][a]});
		if (st[1][a] != -1)
			avl.pb({dist[1][a], a, st[1][a]});
	}


	ll ans = inf;
	for (int i = 0; i < avl.size(); i++) {
		for (int j = i+1; j < avl.size(); j++) {
			vi temp;
			temp.pb(avl[i][1]); temp.pb(avl[i][2]);
			temp.pb(avl[j][1]); temp.pb(avl[j][2]);

			era(temp);

			if (temp.size() == 4) {
				ans = min(ans, avl[i][0] + avl[j][0]);
				if (ans == 2) break;
			}

		}
		if (ans == 2) break;
	}

	cout << ans << endl;








}

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