Submission #1331178

#TimeUsernameProblemLanguageResultExecution timeMemory
1331178MatthewwwwRelay Marathon (NOI20_relaymarathon)C++17
42 / 100
6084 ms275016 KiB
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif
#define data ahhhhh
 
const int sz = 4;
 
struct data {
	array<pair<int, int>, 4> things = {make_pair(-1, -1), make_pair(-1, -1), make_pair(-1, -1), make_pair(-1, -1)};
	bool add (pair<int, int> x) {
		for (int i = 0; i < 4; i++) {
			if (things[i].s == x.s) return false;
			else if (!~things[i].s) {
				things[i] = x;
				return true;
			}
		}
		return false;
	}
	bool can (int x) { 
		for (int i = 0; i < 4; i++) if (things[i].s == x) return false;
		return !~things[3].s;
	}
	vector<pair<int, int>> get() {
		vector<pair<int, int>> vt;
		for (auto i: things) if (~i.s) vt.push_back(i);
		sort(vt.begin(), vt.end());
		vt.erase(vt.begin());
		return vt;
	}
};
 
signed main (signed argc, char **argv) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<pair<int, int>>> adj(n);
	for (int a, b, c; m--;) {
		cin >> a >> b >> c;
		adj[--a].push_back({--b, c});
		adj[b].push_back({a, c});
	}
	vector<data> dt(n);
	priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> pq;
	vector<bool> jh(n, 0);
	for (int a; k--;) {
		cin >> a;
		jh[--a] = 1;
		pq.push({{0, a}, a});
	}
	while (pq.size()) {
		if (dt[pq.top().s].add(pq.top().f)) 
			for (auto i: adj[pq.top().s]) if (dt[i.f].can(pq.top().f.s))
				pq.push({{pq.top().f.f+i.s, pq.top().f.s}, i.f});
		pq.pop();
	}
	vector<vector<pair<int, int>>> res;
	vector<pair<int, pair<int, int>>> lst;
	for (int i = 0; i < n; i++) if (jh[i]) {
		res.push_back(dt[i].get());
		for (auto j: res.back()) if (i < j.s) lst.push_back({j.f, {i, j.s}});
	} else res.push_back({});
	sort(lst.begin(), lst.end());
	int ans = lst[0].f;
	auto unq = [&](vector<int> v) { sort(v.begin(), v.end()); return unique(v.begin(), v.end()) == v.end();};
	for (int i = 1; i < n; i++) if (unq({lst[0].s.f, lst[0].s.s, lst[i].s.f, lst[i].s.s})) {
		ans += lst[i].f;
		break;
	}
	for (auto i: res[lst[0].s.f]) for (auto j: res[lst[0].s.s]) 
		if (unq({lst[0].s.f, lst[0].s.s, i.s, j.s})) ans = min(ans, i.f+j.f);
	cout << ans << "\n";
}
 
/*
*
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃   ━   ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃   ┻   ┃ 
* ┗━┓   ┏━┛  + + 
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the llama protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃        ┣┓
*   ┃        ┏┛
*   ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/
 
//thanks cindy
 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...