제출 #1303093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303093		samarthkulkarni	Relay Marathon (NOI20_relaymarathon)	C++20	0 / 100	6111 ms	513980 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[N][3];
int st[N][3];


void solution() {
	memset(st, -1, sizeof(st));

	for (int i = 0; i < N; i++) {
		dist[i][0] = dist[i][1] = dist[i][2] = 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[a][0] == -1) {
			dist[a][0] = d;
			st[a][0] = from;
		} else if (st[a][1] == -1) {
			dist[a][1] = d;
			st[a][1] = from;
		} else {
			dist[a][2] = d;
			st[a][2] = 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[a][2] != -1 || f == a ||
			st[a][0] == f || st[a][1] == f || st[a][2] == f) continue;

		cal(a, f, -d);

		for (auto [b, w] : adj[a]) {

			if (st[b][0] == f || st[b][1] == f || st[b][2] == f ||
				f == b || st[b][2] != -1) continue;
				
			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[a][0] != -1)
			avl.pb({dist[a][0], a, st[a][0]});
		if (st[a][1] != -1)
			avl.pb({dist[a][1], a, st[a][1]});
		if (st[2][a] != -1) 
			avl.pb({dist[a][2], a, st[a][2]});
	}


	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