제출 #1303036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303036		samarthkulkarni	Relay Marathon (NOI20_relaymarathon)	C++20	5 / 100	6107 ms	512164 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});
	}


	set<int> v;
	for (int i = 0; i < k; i++) {
		int x; cin >> x;
		v.insert(x);
	}


	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[0][a] != -1 && 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});
		}
	}



	vector<array<ll, 3>> avl;
	set<pr> hs;
	hs.insert({0, 0});


	for (auto a : v) {
		pr t1, t2;
		if (st[0][a] != -1) {
			t1 = {min(a, st[0][a]), max(a, st[0][a])};
		}
		if (st[1][a] != -1) {
			t2 = {min(a, st[1][a]), max(a, st[1][a])};
		}

		if (!hs.count(t1)) {
			avl.push_back({dist[0][a], t1.ff, t1.ss});
			hs.insert(t1);
		}
		if (!hs.count(t2)) {
			avl.push_back({dist[1][a], t2.ff, t2.ss});
			hs.insert(t2);
		}
	}


	sort(all(avl));


	ll ans = inf;

	for (int i = 0; i < avl.size(); i++) {
		for (int j = i+1; j < avl.size(); j++) {

			set<int> temp;
			temp.insert(avl[i][1]); temp.insert(avl[i][2]);
			temp.insert(avl[j][1]); temp.insert(avl[j][2]);


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

		}
	}

	cout << ans << endl;






}

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