| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 720272 | thimote75 | 공장들 (JOI14_factories) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define num long long
#define t_road pair<int, num>
#define rnext first
#define rcost second
#define t_roads vector<t_road>
#define graph vector<t_roads>
#define idata vector<int>
#define ndata vector<num>
#define inf 1e18
int nbNodes, nbQuery;
graph roads;
num dfs (int node, int parent, ndata &res) {
for (t_road road : roads[node]) if (road.rnext != parent)
res[node] = min(res[node], dfs(road.rnext, node, res) + road.rcost);
return res[node];
}
ndata dist_state (idata query) {
ndata res(nbNodes, inf);
for (int u : query) res[u] = 0;
dfs(0, -1, res);
return res;
}
ndata read (int size) {
idata mu(size);
for (int i = 0; i < size; i ++)
cin >> mu[i];
return dist_state(mu);
}
int main () {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> nbNodes >> nbQuery;
roads.resize(nbNodes);
for (int iR = 1; iR < nbNodes; iR ++) {
int a, b, c;
cin >> a >> b >> c;
roads[a].push_back({ b, c });
roads[b].push_back({ a, c });
}
for (int idQuery = 0; idQuery < nbQuery; idQuery ++) {
int s, t;
cin >> s >> t;
ndata S, T;
S = read(s);
T = read(t);
num result = inf;
for (int i = 0; i < nbNodes; i ++)
result = min(result, S[i] + T[i]);
cout << result << endl;
}
}