제출 #604237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604237		ziduo	Museum (CEOI17_museum)	C++14	100 / 100	468 ms	746064 KiB

museum

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int n, k, x, cnt[10001], dp[10001][10001][2];
vector<pair<int, int>> edges[10001];
void subSize(int cur, int par){
    cnt[cur] = 1;
    for(pair<int, int> i:edges[cur] ){
        if(i.f==par)continue;
        subSize(i.f, cur);
        cnt[cur]+=cnt[i.f];
    }
}
void dfs(int cur, int par){
    int currSize=1;
    for(pair<int, int> i: edges[cur]){
        if(i.f==par)continue;
        dfs(i.f, cur);
        for(int j=currSize; j>=1; j--){
            for(int m=cnt[i.f]; m>=1; m--){
                dp[cur][j+m][0]=min(min(dp[cur][j+m][0],dp[cur][j][1]+dp[i.f][m][0]+i.s),dp[cur][j][0]+dp[i.f][m][1]+2*i.s);
                dp[cur][j+m][1]=min(dp[cur][j+m][1],dp[cur][j][1]+dp[i.f][m][1] + 2*i.s);
            }
        }
        currSize+=cnt[i.f];
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    cin>>n>>k>>x;
    x--;
   for(int i=0; i<n-1; i++){
        int a, b, c;
        cin>>a>>b>>c;
        a--;b--;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    for(int i=0; i<=n; i++)for(int j=2; j<=k; j++)dp[i][j][0]=dp[i][j][1]=1000000000;
    subSize(x, -1);
    dfs(x, -1);
    cout<<dp[x][k][0]<<endl;
}

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