이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#ifndef LOCAL
#include "factories.h"
#endif
using namespace std;
const int MXN = 500000;
const int64_t INF = 1e18;
int N;
vector<pair<int, int64_t>> g[MXN];
void Init(int n, int A[], int B[], int D[]){
N = n;
for(int i = 0; i < n-1; i++){
g[A[i]].emplace_back(B[i], D[i]);
g[B[i]].emplace_back(A[i], D[i]);
}
}
long long Query(int S, int X[], int T, int Y[]){
vector<int64_t> dis(N, INF);
priority_queue< pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>> > pq;
for(int i = 0; i < S; i++){
dis[X[i]] = 0;
pq.emplace(dis[X[i]], X[i]);
}
vector<int> vis(N);
while(!pq.empty()){
auto [d, u] = pq.top();
pq.pop();
if(vis[u])
continue;
vis[u] = 1;
for(auto& [v, di] : g[u]){
if(dis[v] > dis[u] + di){
dis[v] = dis[u] + di;
pq.emplace(dis[v], v);
}
}
}
int64_t ans = INF;
for(int i = 0; i < T; i++)
ans = min(ans, dis[Y[i]]);
return ans;
}
#ifdef LOCAL
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, Q;
cin >> N >> Q;
int A[N-1], B[N-1], D[N-1];
for(int i = 0; i < N-1; i++){
cin >> A[i] >> B[i] >> D[i];
}
Init(N, A, B, D);
for(int i = 0; i < Q; i++){
int S, T;
cin >> S >> T;
int X[S], Y[T];
for(int j = 0; j < S; j++)
cin >> X[j];
for(int j = 0; j < T; j++)
cin >> Y[j];
cout << Query(S, X, T, Y) << '\n';
}
return 0;
}
#endif
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |