Submission #1053080

#TimeUsernameProblemLanguageResultExecution timeMemory
1053080manhlinh1501Factories (JOI14_factories)C++17
0 / 100
24 ms58972 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; using pii = pair<int, int>; const int MAXN = 5e5 + 5; const i64 oo64 = 1e18; using pli = pair<i64, int>; int N, Q; vector<pii> adj[MAXN]; namespace subtask1{ } void Init(int N, int A[], int B[], int D[]) { for(int i = 0; i < N - 1; i++) { int u = A[i]; int v = B[i]; int w = D[i]; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } } i64 Query(int S, int X[], int T, int Y[]) { vector<i64> dist(N, oo64); priority_queue<pli, vector<pli>, greater<pli>> Q; for(int i = 0; i < S; i++) { int u = X[i]; dist[u] = 0; Q.emplace(dist[u], u); } while(!Q.empty()) { pli top = Q.top(); Q.pop(); int u = top.second; if(top.first != dist[u]) continue; for(pii _ : adj[u]) { int v = _.first; int w = _.second; if(dist[v] > dist[u] + w) { dist[v] = dist[u] + w; Q.emplace(dist[v], v); } } } i64 ans = oo64; for(int i = 0; i < T; i++) { int u = Y[i]; ans = min(ans, dist[u]); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...