Submission #104504

#TimeUsernameProblemLanguageResultExecution timeMemory
104504dfistricCrocodile's Underground City (IOI11_crocodile)C++14
100 / 100
1637 ms86392 KiB
#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) #define ll long long #define X first #define Y second using namespace std; const int MAXN = 100100; ll inf = (1LL << 60); vector <pair <int, ll> > ve[MAXN]; int n, m; ll A[MAXN], B[MAXN]; set <pair <ll, int> > se; int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { n = N, m = M; REP(i, m) { int a = R[i][0], b = R[i][1]; ll c = L[i]; ve[a].push_back({b, c}); ve[b].push_back({a, c}); } REP(i, n) A[i] = B[i] = inf; REP(i, K) A[P[i]] = B[P[i]] = 0; REP(i, n) se.insert({B[i], i}); while (se.size()) { auto tr = *se.begin(); se.erase(se.begin()); int x = tr.Y; for (auto t : ve[x]) { int y = t.X; ll d = tr.X + t.Y; if (d < B[y]) { se.erase({B[y], y}); B[y] = d; if (A[y] > B[y]) swap(A[y], B[y]); se.insert({B[y], y}); } } } return B[0]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...