# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1248122 | quocbaoo | Museum (CEOI17_museum) | C++20 | 426 ms | 746336 KiB |
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=1e4,INF=5e8+9;
int n,dp[N+5][N+5][2],sz[N+5];
vector<pair<int,int>> g[N+5];
void dfs(int u,int pa){
dp[u][1][0]=0;dp[u][1][1]=0;sz[u]=1;
for (auto j:g[u]){
if (j.fi==pa) continue;
dfs(j.fi,u);
for (int j1=sz[u];j1>=1;j1--){
for (int j2=sz[j.fi];j2>=1;j2--){
dp[u][j1+j2][0]=min(dp[u][j1+j2][0],dp[u][j1][0]+dp[j.fi][j2][0]+2*j.se);
dp[u][j1+j2][1]=min(dp[u][j1+j2][1],dp[u][j1][1]+dp[j.fi][j2][0]+2*j.se);
dp[u][j1+j2][1]=min(dp[u][j1+j2][1],dp[u][j1][0]+dp[j.fi][j2][1]+j.se);
}
}
sz[u]+=sz[j.fi];
}
}
int main(){
if (fopen("museum.inp","r")){
freopen("museum.inp","r",stdin);
freopen("museum.out","w",stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
int k,x;cin>>k>>x;
for (int i=1;i<n;i++){
int u,v,w;cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
for (int i=1;i<=n;i++){
for (int j=0;j<=k;j++) dp[i][j][0]=INF,dp[i][j][1]=INF;
}
dfs(x,x);
cout<<dp[x][k][1];
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |