Submission #1303087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303087		samarthkulkarni	Relay Marathon (NOI20_relaymarathon)	C++20	0 / 100	6096 ms	514280 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[3][N];
int st[3][N];
int vis[N];


void solution() {
	memset(st, -1, sizeof(st));
	fill(dist[0], dist[0]+N, inf);
	fill(dist[1], dist[1]+N, inf);
	fill(dist[2], dist[2]+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 (st[0][a] == -1) {
			dist[0][a] = d;
			st[0][a] = from;
		} else if (st[1][a] == -1) {
			dist[1][a] = d;
			st[1][a] = from;
		} else {
			dist[2][a] = d;
			st[2][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 (vis[a] >= 3 || f == a ||
			st[0][a] == f || st[1][a] == f || st[2][a] == f) continue;

		cal(a, f, -d);
		vis[a]++;

		for (auto [b, w] : adj[a]) {
			if (st[2][b] == -1)
				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]});
		if (st[2][a] != -1) 
			avl.pb({dist[2][a], a, st[2][a]});
	}


	sort(all(avl));
	ll ans = inf;

	for (int i = 0; i < avl.size(); i++) {
		if (min(avl[i][1], avl[i][2]) != 1 && 
			max(avl[i][1], avl[i][2]) != 2) {
			ans = min(ans, 1 + avl[i][0]);
			break;
		}
	}
	cout << ans << endl;
	return;


	// 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]);
	// 		}

	// 	}
	// }

	// cout << ans << endl;


}

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