Submission #1004666

#TimeUsernameProblemLanguageResultExecution timeMemory
1004666vjudge3Crocodile's Underground City (IOI11_crocodile)C++17
100 / 100
287 ms63432 KiB
#include "crocodile.h" #include <bits/stdc++.h> using namespace std; vector<pair<int, int>> g[100005]; int di[100005][2]; bool vis[100005]; const int inf = 2e9; int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { for (int i = 0; i < N; i++) di[i][0] = di[i][1] = inf; for (int i = 0; i < M; i++) { g[R[i][0]].push_back({R[i][1], L[i]}); g[R[i][1]].push_back({R[i][0], L[i]}); } using T = pair<int, int>; priority_queue<T, vector<T>, greater<T>> pq; for (int i = 0; i < K; i++) { pq.push({0, P[i]}); di[P[i]][0] = di[P[i]][1] = 0; } while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (di[u][1] != d) continue; if (vis[u]) continue; vis[u] = true; for (auto& [v, w] : g[u]) { if (d+w <= di[v][0]) { di[v][1] = di[v][0]; di[v][0] = d+w; pq.push({di[v][1], v}); } else if (d+w < di[v][1]) { di[v][1] = d+w; pq.push({di[v][1], v}); } } } return di[0][1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...