제출 #336811

#제출 시각아이디문제언어결과실행 시간메모리
336811ScarletSMuseum (CEOI17_museum)C++17
0 / 100
1714 ms1048576 KiB
#include <bits/stdc++.h> #define pii pair<int,int> #define f first #define s second using namespace std; const int mn = 1e4+1, INF=1e9; int dp[2][mn][mn],sub[mn],k; vector<pii> edges[mn]; void dfs(int c, int p) { sub[c]=1; dp[0][c][1]=0; for (pii i : edges[c]) if (i.f!=p) { dfs(i.f,c); sub[c]+=sub[i.f]; for (int j=sub[c];j>1;++j) for (int K=1;K<=sub[i.f];++K) { dp[0][c][j]=min(dp[0][c][j],dp[0][c][j-K]+dp[0][i.f][K]+2*i.s); dp[1][c][j]=min(dp[1][c][j],dp[0][c][j-K]+dp[1][i.f][K]); } } //cout<<c<<" "<<sub[c]<<"\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n,x,a,b,c; cin>>n>>k>>x; for (int i=1;i<n;++i) { cin>>a>>b>>c; edges[a].push_back({b,c}); edges[b].push_back({a,c}); } for (int i=1;i<=n;++i) for (int j=1;j<=k;++j) { dp[0][i][j]=INF; dp[1][i][j]=INF; } dfs(x,0); cout<<dp[1][x][k]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...