#include<bits/stdc++.h>
using namespace std;
#define N 10005
#define son v.first
#define len v.second
inline int read(){
int re=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(isdigit(ch)){
re=re*10+ch-'0';
ch=getchar();
}
return re*f;
}
int dp[N][N][2];
int n,p,Son[N],rt;
vector<pair<int,int>> G[N];
inline void dfs(int now,int fa){
dp[now][1][1]=dp[now][1][0]=0;
Son[now]=1;
for(auto&v:G[now]){
if(son!=fa){
dfs(son,now);
for(int i=min(p,Son[now]);i>0;i--){
if(i-1<=Son[son]){
dp[now][i][1]=min(dp[now][i][1],dp[son][i-1][1]+len);
dp[now][i][0]=min(dp[now][i][0],dp[son][i-1][0]+2*len);
}
for(int j=min({p,Son[son],i});j>=0;j--){
dp[now][i][0]=min(dp[now][i][0],dp[now][i-j][0]+dp[son][j][0]+2*len);
dp[now][i][1]=min(dp[now][i][1],dp[now][i-j][0]+dp[son][j][1]+len);
dp[now][i][1]=min(dp[now][i][1],dp[now][i-j][1]+dp[son][j][0]+2*len);
}
}
Son[now]+=Son[son];
}
}
}
signed main(){
n=read();p=read();rt=read();
for(int i=1,x,y,z;i<n;i++){
x=read();y=read();z=read();
G[x].push_back(make_pair(y,z));
G[y].push_back(make_pair(x,z));
}
for(int i=0;i<=n;i++){
for(int j=0;j<=p;j++){
dp[i][j][1]=dp[i][j][0]=1e9;
}
}
dfs(rt,0);
// for(int i=1;i<=n;i++){
// for(int j=1;j<=p;j++){
// cout<<i<<" visit "<<j<<" :"<<dp[i][j][0]<<" "<<dp[i][j][1]<<endl;
// }
// }
printf("%d",min(dp[rt][p][1],dp[rt][p][0]));
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
46 ms |
265524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
46 ms |
265524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
