#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
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
12236 KB |
Output is correct |
2 |
Correct |
3535 ms |
20548 KB |
Output is correct |
3 |
Correct |
3505 ms |
20716 KB |
Output is correct |
4 |
Correct |
2775 ms |
20616 KB |
Output is correct |
5 |
Correct |
2068 ms |
20652 KB |
Output is correct |
6 |
Correct |
3801 ms |
20840 KB |
Output is correct |
7 |
Correct |
3454 ms |
20628 KB |
Output is correct |
8 |
Correct |
3384 ms |
20676 KB |
Output is correct |
9 |
Correct |
2028 ms |
20580 KB |
Output is correct |
10 |
Correct |
3845 ms |
20864 KB |
Output is correct |
11 |
Correct |
3495 ms |
20484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
12108 KB |
Output is correct |
2 |
Execution timed out |
8029 ms |
56864 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
12236 KB |
Output is correct |
2 |
Correct |
3535 ms |
20548 KB |
Output is correct |
3 |
Correct |
3505 ms |
20716 KB |
Output is correct |
4 |
Correct |
2775 ms |
20616 KB |
Output is correct |
5 |
Correct |
2068 ms |
20652 KB |
Output is correct |
6 |
Correct |
3801 ms |
20840 KB |
Output is correct |
7 |
Correct |
3454 ms |
20628 KB |
Output is correct |
8 |
Correct |
3384 ms |
20676 KB |
Output is correct |
9 |
Correct |
2028 ms |
20580 KB |
Output is correct |
10 |
Correct |
3845 ms |
20864 KB |
Output is correct |
11 |
Correct |
3495 ms |
20484 KB |
Output is correct |
12 |
Correct |
33 ms |
12108 KB |
Output is correct |
13 |
Execution timed out |
8029 ms |
56864 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |