Submission #952154

#	Time	Username	Problem	Language	Result	Execution time	Memory
952154		vjudge1	Museum (CEOI17_museum)	C++14	0 / 100	355 ms	784464 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 j=1;j<=min(son[v.first],k);j++){
			for(int i=min(k,son[u]-son[v.first]+j);i>=j+1;i--){
				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: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20