Submission #367710

#TimeUsernameProblemLanguageResultExecution timeMemory
367710arujbansalRelay Marathon (NOI20_relaymarathon)C++17
0 / 100
3487 ms67816 KiB
#include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #include <array> #include <stack> #include <queue> #include <random> #include <numeric> #include <functional> #include <chrono> #include <utility> #include <iomanip> #include <assert.h> using namespace std; void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define rng_seed(x) mt19937 rng(x) #define all(x) (x).begin(), (x).end() #define sz(x) (int) (x).size() // #define int long long rng_init; const int MXN = 1e5 + 5, INF = 1e9 + 5; int N, M, K; vector<pair<int, int>> g[MXN]; int dijkstra(const vector<int> &src, const vector<int> &sink) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; vector<int> dist(N, INF); for (const auto &x : src) { dist[x] = 0; pq.emplace(0, x); } vector<bool> finish(N, false); for (const auto &x : sink) finish[x] = true; while (!pq.empty()) { auto cur = pq.top(); pq.pop(); int u = cur.second, cur_dist = cur.first; if (cur_dist > dist[u]) continue; if (finish[u]) return cur_dist; for (const auto &[v, wt] : g[u]) { int new_dist = cur_dist + wt; if (new_dist < dist[v]) { dist[v] = new_dist; pq.emplace(new_dist, v); } } } int ans = INF; for (const auto &x : sink) ans = min(ans, dist[x]); return ans; } void solve() { cin >> N >> M >> K; for (int i = 0; i < M; i++) { int u, v, w; cin >> u >> v >> w; u--, v--; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } vector<int> special(K); for (auto &x : special) { cin >> x; x--; } int ans = INF; for (int iter = 0; iter < 50; iter++) { shuffle(all(special), rng); vector<int> src[2], sink[2]; for (int i = 0; i < K; i++) { if (i < K / 4) src[0].push_back(special[i]); else if (i < K / 2) sink[0].push_back(special[i]); else if (i < 3 * K / 4) src[1].push_back(special[i]); else sink[1].push_back(special[i]); } ans = min(ans, dijkstra(src[0], sink[0]) + dijkstra(src[1], sink[1])); } cout << ans; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int TC = 1; // cin >> TC; while (TC--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...