#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
const int inf = 1000000000;
int n, k, start;
vector<pair<int, int>> g[maxn];
int dp1[maxn][maxn];
int dp2[maxn][maxn];
int subtree_size[maxn];
void dfs(int node, int par)
{
subtree_size[node] = 1;
for (auto [next_node, w] : g[node])
{
if (next_node != par)
{
dfs(next_node, node);
}
}
dp1[node][1] = 0;
dp2[node][1] = 0;
for (auto [next_node, w] : g[node])
{
if (next_node != node)
{
for (int i = subtree_size[node]; i >= 0; --i)
{
for (int j = subtree_size[next_node]; j >= 0; --j)
{
dp1[node][i + j] = min(dp1[node][i + j], dp1[node][i] + dp1[next_node][j] + 2 * w);
dp2[node][i + j] = min(dp2[node][i + j], dp2[node][i] + dp1[next_node][j] + 2 * w);
dp2[node][i + j] = min(dp2[node][i + j], dp1[node][i] + dp2[next_node][j] + 1 * w);
dp2[node][i + j] = min(dp2[node][i + j], dp1[node][i] + dp1[next_node][j] + 1 * w);
}
}
subtree_size[node] += subtree_size[next_node];
}
}
}
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
cin >> n >> k >> start;
for (int i = 1; i <= n - 1; ++i)
{
int x, y, w;
cin >> x >> y >> w;
g[x].push_back(make_pair(y, w));
g[y].push_back(make_pair(x, w));
}
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= n; ++j)
{
dp1[i][j] = inf;
dp2[i][j] = inf;
}
}
dfs(start, -1);
cout << dp2[start][k] << endl;
return 0;
}
/*
11 8 3
1 3 3
3 2 5
6 4 5
1 11 3
9 1 2
9 10 2
3 7 10
6 7 1
7 8 1
7 5 1
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
688 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
871 ms |
784376 KB |
Output is correct |
2 |
Correct |
866 ms |
784372 KB |
Output is correct |
3 |
Incorrect |
1073 ms |
784828 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
871 ms |
784376 KB |
Output is correct |
2 |
Correct |
866 ms |
784372 KB |
Output is correct |
3 |
Incorrect |
1073 ms |
784828 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
688 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
692 KB |
Output is correct |
6 |
Correct |
871 ms |
784376 KB |
Output is correct |
7 |
Correct |
866 ms |
784372 KB |
Output is correct |
8 |
Incorrect |
1073 ms |
784828 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |