#include <stdio.h> #include <vector> int n, k, x; int dp[10005][10005][2]; std::vector<std::pair<int, int> > vec[10005]; int dfs(int, int); int main() { // freopen("museum.in", "r", stdin); // freopen("museum.out", "w", stdout); scanf("%d%d%d", &n, &k, &x); for(int i = 1, a, b, c; i < n; ++i) { scanf("%d%d%d", &a, &b, &c); vec[a].push_back({b, c}); vec[b].push_back({a, c}); } dfs(x, 0); printf("%d\n", dp[x][k][1]); return 0; } int dfs(int root, int fa) { int siz = 1; for(auto v : vec[root]) if(v.first != fa) { int p = dfs(v.first, root); for(int i = siz + 1; i <= siz + p; ++i) dp[root][i][0] = dp[root][i][1] = 0x7f7f7f7f; for(int i = std::min(siz + p, k); i >= 0; --i) for(int j = std::max(0, i - siz); j <= p && j <= i; ++j) { dp[root][i][1] = std::min(dp[root][i][1], dp[root][i - j][0] + dp[v.first][j][1] + v.second); dp[root][i][1] = std::min(dp[root][i][1], dp[root][i - j][1] + dp[v.first][j][0] + (v.second << 1)); dp[root][i][0] = std::min(dp[root][i][0], dp[root][i - j][0] + dp[v.first][j][0] + (v.second << 1)); } siz += p; } return siz; }

museum.cpp: In function 'int main()':
museum.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d%d%d", &n, &k, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
museum.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%d%d%d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~