/**
* author : Lăng Trọng Đạt
* created: 14-06-2024
**/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e4 + 5;
const int INF = 1e18;
int g[MAXN];
vector<pair<int, int>> adj[MAXN];
int n;
vector<int> dp[MAXN][2]; // dp[i][j][t]: thời gian tối thiểu để thăm quan j phòng phân biệt khi đi từ node i
// t = 0: đi và đã trở về i
// t = 1: đi và dừng tại địa điểm thứ j
vector<int> min_time(vector<int>& a, vector<int>& b, int w) {
vector<int> res(a.size() + b.size() - 1, INF);
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < b.size(); j++)
res[i + j] = min(res[i + j], a[i] + b[j] + (j > 0 ? w : 0));
return res;
}
void dfs(int v, int prv) {
dp[v][0] = {0, 0};
dp[v][1] = {0, 0};
vector<pair<int, int>> chill;
vector<int> suf = {0};
vector<vector<int>> pref;
pref.push_back(dp[v][1]);
for (auto[u, w] : adj[v]) {
if (u == prv) continue;
chill.push_back({u, w});
// db(v, u)
dfs(u, v);
dp[v][0] = min_time(dp[v][0], dp[u][0], 2*w);
pref.push_back(dp[v][0]);
}
pref.pop_back();
// db(v, chill)
for (int i = chill.size() - 1; i >= 0; i--) {
int u = chill[i].first, w = chill[i].second;
// db(i, pref.size())
vector<int> tmp = min_time(pref.back(), suf, 0);
dp[u][1][0] = INF;
vector<int> tmp2 = min_time(tmp, dp[u][1], w);
for (int j = 1; j < tmp2.size(); j++) {
if (j < dp[v][1].size()) dp[v][1][j] = min(dp[v][1][j], tmp2[j]);
else dp[v][1].push_back(tmp2[j]);
}
// if (v == 1 && dp[v][1].size() > 4 && dp[v][1][4] == 6) {
// db(u, w, suf, pref.back(), dp[u][1])
// db(tmp)
// db(tmp2)
// exit(0);
// }
suf = min_time(suf, dp[u][1], 2*w);
pref.pop_back();
}
// db(dp[v][0])
// db(dp[v][1])
}
main() {
// freopen("hi.inp", "r", stdin);
int k, root;
cin >> n >> k >> root;
int a, b, c;
for (int i = 1; i < n; i++) {
cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
dfs(root, -1);
// db("fuck")
cout << dp[root][1][k];
}
Compilation message
museum.cpp: In function 'std::vector<long long int> min_time(std::vector<long long int>&, std::vector<long long int>&, long long int)':
museum.cpp:20:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (int i = 0; i < a.size(); i++)
| ~~^~~~~~~~~~
museum.cpp:21:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for (int j = 0; j < b.size(); j++)
| ~~^~~~~~~~~~
museum.cpp: In function 'void dfs(long long int, long long int)':
museum.cpp:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
32 | for (auto[u, w] : adj[v]) {
| ^
museum.cpp:48:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int j = 1; j < tmp2.size(); j++) {
| ~~^~~~~~~~~~~~~
museum.cpp:49:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | if (j < dp[v][1].size()) dp[v][1][j] = min(dp[v][1][j], tmp2[j]);
| ~~^~~~~~~~~~~~~~~~~
museum.cpp: At global scope:
museum.cpp:64:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
64 | main() {
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
1112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
156 ms |
6800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
156 ms |
6800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
1112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
