| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 883305 | 2023-12-05T06:23:09 Z | vjudge1 | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1'000'000'000'000'000'000;
const int N = 5000;
int n, q;
ll dis[N + 10];
vector<pair<int, ll>> adj[N + 10];
vector<int> vec1, vec2;
void readInput() {
cin >> n >> q;
for (int i = 1; i < n; i++) {
int u, v;
ll w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
}
void dij() {
fill(dis + 1, dis + n + 1, INF);
set<pair<ll, int>> st;
for (auto t: vec1) {
dis[t] = 0;
st.insert({0, t});
}
while (!st.empty()) {
int u = st.begin() -> second;
st.erase(st.begin());
for (auto [v, w]: adj[u])
if (dis[u] + w < dis[v]) {
st.erase({dis[v], v});
dis[v] = dis[u] + w;
st.insert({dis[v], v});
}
}
}
void query() {
int x, y;
cin >> x >> y;
for (int i = 1; i <= x; i++) {
int t;
cin >> t;
vec1.push_back(t);
}
for (int i = 1; i <= y; i++) {
int t;
cin >> t;
vec2.push_back(t);
}
dij();
ll mn = INF;
for (auto t: vec2)
mn = min(mn, dis[t]);
cout << mn << '\n';
vec1.clear();
vec2.clear();
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
readInput();
while (q--)
query();
cout.flush();
return 0;
}