제출 #1166414

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166414		dosts	Museum (CEOI17_museum)	C++17	100 / 100	322 ms	344052 KiB

museum

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sp << " " << 
using namespace std;

const int N = 10001,MOD = 998244353,inf = 1e18;

vi cnt(N,0),sz(N,0);
vector<pii> edges[N];
vi dp[N],dp2[N];
void dfs(int node,int p) {
    sz[node] = 1;
    dp[node] = {inf,0};
    dp2[node] = {inf,0};
    for (auto it : edges[node]) {
        if (it.ff == p) continue;
        dfs(it.ff,node);
        while (dp[node].size() < sz[node]+sz[it.ff]+1) dp[node].push_back(inf);
        while (dp2[node].size() < sz[node]+sz[it.ff]+1) dp2[node].push_back(inf);
        vi dpp = dp[node],dppp = dp2[node];
        for (int j = 1;j<=sz[node];j++) {
            for (int k = 1;k<=sz[it.ff];k++) {
                dp2[node][j+k] = min(dp2[node][j+k],dppp[j]+dp2[it.ff][k]+2*it.ss);
                dp[node][j+k] = min(dp[node][j+k],dpp[j]+dp2[it.ff][k]+2*it.ss);
                dp[node][j+k] = min(dp[node][j+k],dppp[j]+dp[it.ff][k]+it.ss);
            }
        }
        dp[it.ff].clear();
        dp2[it.ff].clear();
        sz[node]+=sz[it.ff];
    }
}

void solve() {
    int n,k,x;
    cin >> n >> k >> x;
    for (int i=1;i<=n-1;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    dfs(x,x);
    cout << dp[x][k] << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
} 

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