Submission #952156

#	Time	Username	Problem	Language	Result	Execution time	Memory
952156		vjudge1	Museum (CEOI17_museum)	C++14	80 / 100	3062 ms	785192 KiB

museum

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,k,x,son[N];
int dp[N][N][2];
vector<pair<int,int> >g[N];
inline void dfs(int u,int fa){
	dp[u][1][0]=dp[u][1][1]=0;
	son[u]=1;
	for(auto v:g[u]){
		if(v.first==fa)continue;
		dfs(v.first,u);
		son[u]+=son[v.first];
		for(int i=min(k,son[u]);i>=2;i--){
			for(int j=min(i,son[v.first]);j>=0;j--){
				if(dp[u][i-j][0]+dp[v.first][j][0]+v.second*2>=0)dp[u][i][0]=min(dp[u][i][0],dp[u][i-j][0]+dp[v.first][j][0]+v.second*2);
				if(dp[u][i-j][0]+dp[v.first][j][1]+v.second>=0)dp[u][i][1]=min(dp[u][i][1],dp[u][i-j][0]+dp[v.first][j][1]+v.second);
				if(dp[u][i-j][1]+dp[v.first][j][0]+v.second*2>=0)dp[u][i][1]=min(dp[u][i][1],dp[u][i-j][1]+dp[v.first][j][0]+v.second*2);
			}
		}
	}
}
int main(){
	//freopen("museum.in","r",stdin);
	//freopen("museum.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(dp,0x7f,sizeof dp);
	cin>>n>>k>>x;
	for(int i=1,a,b,c;i<n;i++){
		cin>>a>>b>>c;
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	dfs(x,-1);
	cout<<min(dp[x][k][0],dp[x][k][1]);
} 

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