# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
951011 | 2024-03-21T04:14:24 Z | efishel | Crocodile's Underground City (IOI11_crocodile) | C++17 | 0 ms | 0 KB |
#include "crocodile.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using vll = vector <ll>; const ll MAXN = 1E5+16; vector <pair <ll, ll> > adj[MAXN]; ll travel_plan (int _n, int _m, int _r[][2], int _l[], int _k, int _p[]) { ll n = _n, m = _m, k = _k; for (ll i = 0; i < m; i++) { ll u = _r[i][0], v = _r[i][1]; ll w = _l[i]; adj[u].push_back({ v, w }); adj[v].push_back({ u, w }); } priority_queue <pair <ll, ll> > pq; vll cvis(n, 0); vector <bool> vis(n, false); vll dis(n); vll srcs(_p, _p+k); for (ll u : srcs) { cvis[u] = 1; dis[u] = 0; pq.push({ -dis[u], u }); } while (pq.size()) { auto [disU, u] = pq.top(); disU = -disU; pq.pop(); cvis[u]++; if (cvis[u] != 2) continue; dis[u] = disU; for (auto [v, w] : adj[u]) { pq.push({ -(dis[u]+w), v }); } } return dis[0]; }