제출 #383079

#제출 시각아이디문제언어결과실행 시간메모리
383079HegdahlRelay Marathon (NOI20_relaymarathon)C++17
5 / 100
6031 ms515688 KiB
#pragma GCC optimize("Ofast") #define _USE_MATH_DEFINES #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #ifdef ENABLE_DEBUG #include <debug.h> #else #define DEBUG(...) do {} while (0) #endif using namespace std; using namespace __gnu_pbds; using ll = long long; using ull = unsigned long long; using lll = __int128; using ulll = unsigned __int128; using ld = long double; template<typename T, size_t N> using ar = array<T, N>; template<typename T, typename Cmp = less<T>> using iset = tree<T, null_type, Cmp, rb_tree_tag, tree_order_statistics_node_update, allocator<T>>; #define REPSI(name, start, stop, step) for (ll name = start; name < (ll)stop; name += step) #define REPS(name, start, stop) REPSI(name, start, stop, 1) #define REP(name, stop) REPS(name, 0, stop) #define RREPSI(name, start, stop, step) for (ll name = stop-1; name >= (ll)start; name -= step) #define RREPS(name, start, stop) RREPSI(name, start, stop, 1) #define RREP(name, stop) RREPS(name, 0, stop) template<typename T> void cins(T &first) { cin >> first; } template<typename T, typename... Ts> void cins(T &first, T &second, Ts&... rest) { cin >> first; cins(second, rest...); } #define GET(type, ...) type __VA_ARGS__; cins(__VA_ARGS__) #define GETI(...) GET(int, __VA_ARGS__) #define GETLL(...) GET(ll, __VA_ARGS__) #define GETS(...) GET(string, __VA_ARGS__) #define GETD(...) GET(double, __VA_ARGS__) #define GETC(...) GET(char, __VA_ARGS__) struct hsh { size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); x += FIXED_RANDOM; x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } }; const ll mxN = 1e5; vector<ar<ll, 2>> g[mxN]; int main() { ios::sync_with_stdio(0);cin.tie(0); GETI(n, m, k); REP(mm, m) { GETI(i, j, w); --i, --j; g[i].push_back({j, w}); g[j].push_back({i, w}); } vector<ll> a(k); REP(i, k) cin >> a[i], --a[i]; vector<bool> special(n); for (ll x : a) special[x] = true; vector<ll> vis_cnt(n); vector<ar<ll, 2>> vis(n, {-1, -1}), dist(n, {-1, -1}); priority_queue<ar<ll, 3>, vector<ar<ll, 3>>, greater<ar<ll, 3>>> pq; for (ll cur : a) for (auto [nxt, w] : g[cur]) pq.push({w, nxt, cur}); while (pq.size()) { auto [dhere, cur, source] = pq.top(); pq.pop(); if (vis_cnt[cur]==2) continue; DEBUG(cur); DEBUG(vis_cnt[cur]); DEBUG(vis[cur]); DEBUG(dist[cur]); bool ok = true; REP(p, vis_cnt[cur]) if (vis[cur][p] == source) ok = false; if (!ok) continue; vis[cur][vis_cnt[cur]] = source; dist[cur][vis_cnt[cur]] = dhere; ++vis_cnt[cur]; for (auto [nxt, w] : g[cur]) { if (vis_cnt[nxt] == 2) continue; if (nxt == source) continue; bool ok = true; REP(p, vis_cnt[nxt]) if (vis[nxt][p] == source) ok = false; if (!ok) continue; pq.push({dhere+w, nxt, source}); } } vector<ar<ll, 3>> pairs; REP(i, n) if (special[i]) REP(p, vis_cnt[i]) if (vis[i][p] != i) pairs.push_back({dist[i][p], min(i, vis[i][p]), max(i, vis[i][p])}); sort(pairs.begin(), pairs.end()); pairs.erase(unique(pairs.begin(), pairs.end()), pairs.end()); DEBUG(pairs); int P = pairs.size(); ll ans = 1LL<<60; REP(p0, min(P, 10)) { auto [d0, i0, j0] = pairs[p0]; REP(p1, min(P, 10)) { auto [d1, i1, j1] = pairs[p1]; if (i0 == i1) continue; if (i0 == j1) continue; if (j0 == i1) continue; if (j0 == j1) continue; ans = min(ans, d0+d1); break; } } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...