Submission #1250596

#TimeUsernameProblemLanguageResultExecution timeMemory
1250596LaMatematica14Crocodile's Underground City (IOI11_crocodile)C++20
100 / 100
291 ms44796 KiB
#include <bits/stdc++.h> using namespace std; int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { vector<vector<pair<int, int>>> adj(N); for (int i = 0; i < M; i++) { adj[R[i][0]].push_back({R[i][1], L[i]}); adj[R[i][1]].push_back({R[i][0], L[i]}); } priority_queue<pair<int, int>> pq; vector<int> b(N, 1e9+7), sb(N, 1e9+7); for (int i = 0; i < K; i++) { pq.push({0, P[i]}); b[P[i]] = 0; sb[P[i]] = 0; } vector<bool> v(N, 0); while (!pq.empty()) { int a = pq.top().second; pq.pop(); if (v[a]) continue; if (sb[a] < 1e9+7) v[a] = 1; else continue; for (pair<int, int> i : adj[a]) { if (b[i.first] > sb[a]+i.second) { sb[i.first] = b[i.first]; b[i.first] = sb[a]+i.second; if (sb[i.first] < 1e9+7) pq.push({-sb[i.first], i.first}); } else if (sb[i.first] > sb[a] + i.second) { sb[i.first] = sb[a]+i.second; pq.push({-sb[i.first], i.first}); } } } return sb[0]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...