제출 #1367933

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1367933		tranvinhhuy2010	Museum (CEOI17_museum)	C++20	100 / 100	176 ms	309568 KiB

museum

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int nmax = 1e4 + 5;
int n, k, x, sz[nmax];
vector <pair <int, ll>> g[nmax];
ll dp[nmax][nmax][2], ndp[nmax][2];

void dfs(int u, int p) {
    sz[u] = 1;
    for (auto [v, w] : g[u]) {
        if (v==p) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }

    int cur = 1;
    for (int i=2; i<=sz[u]; i++)
        dp[u][i][0] = dp[u][i][1] = 1e15;
    for (auto [v, w] : g[u]) {
        if (v==p) continue;

        for (int i=1; i<=cur+sz[v]; i++) {
            ndp[i][0] = dp[u][i][0];
            ndp[i][1] = dp[u][i][1];
        }

        for (int i=1; i<=cur; i++) {
            for (int j=1; j<=sz[v]; j++) {
                ndp[i + j][0] = min(ndp[i + j][0], dp[u][i][0] + dp[v][j][0] + 2 * w);
                ndp[i + j][1] = min(ndp[i + j][1], dp[u][i][0] + w + dp[v][j][1]);
                ndp[i + j][1] = min(ndp[i + j][1], dp[u][i][1] + dp[v][j][0] + 2 * w);
            }
        }

        cur += sz[v];
        for (int i=1; i<=cur; i++) {
            dp[u][i][0] = ndp[i][0];
            dp[u][i][1] = ndp[i][1];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k >> x;
    for (int i=1; i<n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    dfs(x, 0);
    cout << min(dp[x][k][0], dp[x][k][1]);

    return 0;
}

• 서브태스크 1: 20 / 20
• 서브태스크 2: 25 / 25
• 서브태스크 3: 35 / 35
• 서브태스크 4: 20 / 20