#include <bits/stdc++.h>
#define FNAME "RUNNING"
using namespace std;
const int N = 1e4 + 1;
int n, k, s;
vector<pair<int,int>> adj[N];
int sz[N];
int dp[N][N][2];
void Task() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(FNAME".INP","r")) {
freopen(FNAME".INP","r",stdin);
freopen(FNAME".OUT","w",stdout);
}
}
void Input() {
memset(dp, 0x3f, sizeof(dp));
cin >> n >> k >> s;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
}
int limu, limv;
void DFS(int u, int par) {
dp[u][0][0] = 0;
dp[u][1][0] = dp[u][1][1] = 0;
sz[u] = 1;
for (auto e : adj[u]) {
int v, w;
tie(v, w) = e;
if (v ^ par) {
DFS(v, u);
sz[u] += sz[v];
limu = min(sz[u], k);
for (int x = limu; x >= 2; x--) {
limv = min(sz[v], x);
for (int y = 1; y <= limv; y++) {
dp[u][x][0] = min(dp[u][x][0], dp[u][x - y][0] + dp[v][y][0] + w * 2);
dp[u][x][1] = min(dp[u][x][1], dp[u][x - y][0] + w + dp[v][y][1]);
dp[u][x][1] = min(dp[u][x][1], dp[u][x - y][1] + dp[v][y][0] + w * 2);
}
}
}
}
}
void solve() {
DFS(s, s);
cout << min(dp[s][k][0], dp[s][k][1]) << '\n';
}
void Solve() {
Input();
solve();
}
int main() {
Task();
Solve();
return 2231^2231;
}
Compilation message (stderr)
museum.cpp: In function 'void Task()':
museum.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | freopen(FNAME".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen(FNAME".OUT","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |