#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)
#define N 10002
#define ALL(x) x.begin(), x.end()
int dp[N][N][2];
int n, k, x, sz[N];
vector<pair<int, int>> g[N];
/*
* at, take, comebacktonode
*
* dp[u][j][1] = min (t1 + t2 + ... + td == j - 1)
* ( 2w + dp[v][j][1] )
* dp[u][j][0] = min (t1 + t2 + ... + td == j - 1)
* (dp[v1][t1][1]+2*w1 + ... + dp[vd-1][td-1][1]+2*wd-1) + dp[vd][td][0] + wd
*
* ans = dp[x][k][0]
*/
void dfs(int u, int p)
{
sz[u] = 1;
for (auto [w, v] : g[u])
{
if (v == p) continue;
dfs(v, u);
for (int i = sz[u]; i >= 0; --i) for (int j = sz[v]; j >= 1; --j)
{
dp[u][i+j][1] = min(dp[u][i+j][1], 2*w + dp[v][j][1] + dp[u][i][1]);
dp[u][i+j][0] = min(dp[u][i+j][0], 2*w + dp[v][j][0] + dp[u][i][1]);
dp[u][i+j][0] = min(dp[u][i+j][0], w + dp[v][j][0] + dp[u][i][1]);
}
sz[u] += sz[v];
}
}
int main()
{
ShinLena;
cin >> n >> k >> x;
for (int i = 1, u, v, w; i < n; ++i)
cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u);
for (int i = 1; i <= n; ++i) for (int j = 2; j <= k; ++j) dp[i][k][0] = dp[i][k][1] = 2e9;
dfs(x, x);
cout << dp[x][k][0];
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
153 ms |
314196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
153 ms |
314196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
