Submission #367600

#	Time	Username	Problem	Language	Result	Execution time	Memory
367600		Aryan_Raina	Relay Marathon (NOI20_relaymarathon)	C++14	100 / 100	5613 ms	183896 KiB

RelayMarathon

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

#define int long long
#define nl '\n'

const int INF = 1e15;
const int MOD = 1e9+7;

const int MXN = 1e5+9;
vector<array<int,2>> g[MXN];
int n, m, k;
int magic(vector<int> &s, vector<int> &f) {
	priority_queue<array<int,2>, vector<array<int,2>>, greater<array<int,2>>> pq;
	vector<bool> inf(n, 0);
	for (int i : s) pq.push({0, i});
	for (int i : f) inf[i] = 1;
	vector<bool> vis(n, 0);
	while (!pq.empty()) {
		auto u = pq.top();
		pq.pop();
		if (vis[u[1]]) continue;
		vis[u[1]] = 1;
		if (inf[u[1]]) return u[0]; 
		for (auto v : g[u[1]]) if (!vis[v[1]]) {
			pq.push({u[0] + v[0], v[1]});
		}
	}
	return INF;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin>>n>>m>>k;
    for (int i = 0; i < m; i++) {
    	int a, b, wt; cin>>a>>b>>wt;
    	--a, --b;
    	g[a].push_back({wt,b});
    	g[b].push_back({wt,a});
    }
    vector<int> special(k);
    for (int &i : special) cin>>i, --i;

    int ans = INF;
    while (clock() < 5.5*CLOCKS_PER_SEC) {
    	shuffle(special.begin(), special.end(), rng);
    	vector<int> start1, finish1, start2, finish2;
    	for (int i = 0; i < k; i++) {
    		if (i < k/4) start1.push_back(special[i]);
    		else if (i < k/2) finish1.push_back(special[i]);
    		else if (i < 3*k/4) start2.push_back(special[i]);
    		else finish2.push_back(special[i]);
    	}
    	int d = 0;
    	d += magic(start1, finish1);
    	d += magic(start2, finish2);
    	ans = min(d, ans);
    }
    cout<<ans;
}

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