| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 777096 | Phan_Tien_Dung | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int N = 2e5 + 5;
const int INF = 1 << 30;
int n, mn[N], res = INF, k;
vector<pair<int, int>> adj[N];
void Cal(int u, int par, int depth, int dis) {
res = min(res, depth + mn[k - dis]);
for (auto [v, l] : adj[u]) {
if (v == par) {
continue;
}
if (dis + l > k) {
continue;
}
Cal(v, u, depth + 1, dis + l);
}
}
void Update(int u, int par, int depth, int dis) {
mn[dis] = min(mn[dis], depth);
for (auto [v, l] : adj[u]) {
if (v == par) {
continue;
}
if (dis + l > k) {
continue;
}
Update(v, u, depth + 1, dis + l);
}
}
void Process(int s) {
fill(mn + 1, mn + n + 1, INF);
mn[0] = 0;
for (auto [v, l] : adj[s]) {
if (l <= k) {
Cal(v, s, 1, l);
Update(v, s, 1, l);
}
}
}
void Solve() {
cin >> n >> k;
for (int i = 1; i < n; ++i) {
int u, v, l;
cin >> u >> v >> l;
adj[u].push_back({v, l});
adj[v].push_back({u, l});
}
for (int i = 1; i <= n; ++i) {
Process(i);
}
if (res == INF) {
cout << -1;
} else {
cout << res;
}
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
clock_t tStart = clock();
int t = 1;
// cin >> t;
while (t--) {
Solve();
}
cerr << fixed << setprecision(10) << "\nTime Taken:\n" << (double)(clock() - tStart) / CLOCKS_PER_SEC;
}