Submission #864016

#	Time	Username	Problem	Language	Result	Execution time	Memory
864016		sheldon	Museum (CEOI17_museum)	C++14	100 / 100	387 ms	784800 KiB

museum

#include <bits/stdc++.h>

using namespace std;

const int nax = 1e4 + 5;
int dp[nax][nax][2], sz[nax];
vector<pair<int, int>> edges[nax];

void dfs (int u, int p) {
    sz[u] = 1;
    for (pair<int, int> pp : edges[u]) {
        int v = pp.first, c = pp.second;
        if (v != p) {
            dfs (v, u);
            for (int i = sz[u]; i >= 1; --i) {
                for (int j = 1; j <= sz[v]; ++j) {
                    dp[u][i + j][1] = min(dp[u][i + j][1], dp[u][i][0] + dp[v][j][1] + c);
                    dp[u][i + j][1] = min(dp[u][i + j][1], dp[u][i][1] + dp[v][j][0] + c * 2);
                    dp[u][i + j][0] = min(dp[u][i + j][0], dp[u][i][0] + dp[v][j][0] + c * 2);
                }
            }
            sz[u] += sz[v];
        }
    }
}

void solve() {
    int n, k, x;
    cin >> n >> k >> x;
    for (int i = 0; i < n - 1; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        edges[u].push_back({v, c});
        edges[v].push_back({u, c});
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 2; j <= n; ++j) {
            dp[i][j][0] = dp[i][j][1] = 1e9;
        }
    }
    dfs (x, 0);
    cout << dp[x][k][1];
}

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

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20