# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1200049 | IBory | Crocodile's Underground City (IOI11_crocodile) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;
const int MAX = 100007;
vector<pii> G[MAX];
ll D[MAX], V[MAX];
int travel_plan(int N, int M, int* R[2], int* L, int K, int* P) {
for (int i = 0; i < M; ++i) {
ll a = R[i][0], b = R[i][1], c = L[i];
G[a].emplace_back(b, c);
G[b].emplace_back(a, c);
}
priority_queue<pii, vector<pii>, greater<pii>> PQ;
memset(D, 0x3f, sizeof(D));
while (K--) {
int n = P[K];
V[n] = 1;
PQ.emplace(0, n);
}
while (!PQ.empty()) {
auto [cd, cur] = PQ.top(); PQ.pop();
if (++V[cur] != 2) continue;
D[cur] = cd;
for (auto [next, nd] : G[cur]) PQ.emplace(cd + nd, next);
}
return D[0];
}