| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 821090 | Alihan_8 | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
#define int long long
template <class _T>
bool chmin(_T &x, const _T &y){
bool flag = false;
if ( x > y ){
x = y; flag |= true;
}
return flag;
}
template <class _T>
bool chmax(_T &x, const _T &y){
bool flag = false;
if ( x < y ){
x = y; flag |= true;
}
return flag;
}
const int inf = 1e16 + 1;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q; cin >> n >> q;
vector <pair<int,int>> g[n];
for ( int i = 0; i + 1 < n; i++ ){
int x, y, w; cin >> x >> y >> w;
g[x].pb({y, w});
g[y].pb({x, w});
}
while ( q-- ){
int X, Y; cin >> X >> Y;
priority_queue <pair<int,int>> q;
vector <int> dis(n, inf);
for ( int i = 0; i < X; i++ ){
int u; cin >> u;
dis[u] = 0;
q.push({0, u});
}
while ( !q.empty() ){
auto [val, u] = q.top();
q.pop(); val *= -1;
if ( dis[u] != val ){
continue;
}
for ( auto [v, w]: g[u] ){
if ( chmin(dis[v], dis[u] + w) ){
q.push({-dis[v], v});
}
}
}
int ans = inf;
for ( int i = 0; i < Y; i++ ){
int u; cin >> u;
chmin(ans, dis[u]);
}
cout << ans << ln;
}
cout << '\n';
}