#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>adj[10005];
int n,k,x;
int inf=1e9;
int dp[2][10005][10005];
int sz[10005];
void dfs(int u,int p=-1){
//cerr<<u<<"\n";
sz[u]=1;
for(auto x:adj[u])if(x.second!=p){
dfs(x.second,u);
for(int i=sz[u];i>=0;i--){
for(int j=sz[x.second];j>=0;j--){
dp[0][u][i+j]=min(dp[0][u][i+j],dp[0][u][i]+dp[0][x.second][j]+x.first*2);
dp[1][u][i+j]=min({dp[1][u][i+j],dp[0][u][i]+dp[1][x.second][j]+x.first,dp[1][u][i]+dp[0][x.second][j]+x.first*2});
}
}
sz[u]+=sz[x.second];
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k>>x;
for(int i=1;i<=n-1;i++){
int a,b,c;
cin>>a>>b>>c;
adj[a].push_back({c,b});
adj[b].push_back({c,a});
}
for(int i=0;i<=n;i++){
for(int j=2;j<=k;j++){
dp[0][i][j]=dp[1][i][j]=inf;
}
}
//cerr<<"work\n";
dfs(x);
cout<<dp[1][x][k];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Correct |
1 ms |
6748 KB |
Output is correct |
3 |
Correct |
1 ms |
6812 KB |
Output is correct |
4 |
Correct |
1 ms |
6748 KB |
Output is correct |
5 |
Correct |
1 ms |
6748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
333 ms |
557956 KB |
Output is correct |
2 |
Correct |
187 ms |
558124 KB |
Output is correct |
3 |
Correct |
262 ms |
602200 KB |
Output is correct |
4 |
Correct |
198 ms |
573140 KB |
Output is correct |
5 |
Correct |
179 ms |
564312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
333 ms |
557956 KB |
Output is correct |
2 |
Correct |
187 ms |
558124 KB |
Output is correct |
3 |
Correct |
262 ms |
602200 KB |
Output is correct |
4 |
Correct |
198 ms |
573140 KB |
Output is correct |
5 |
Correct |
179 ms |
564312 KB |
Output is correct |
6 |
Correct |
169 ms |
563244 KB |
Output is correct |
7 |
Correct |
222 ms |
588080 KB |
Output is correct |
8 |
Correct |
349 ms |
563284 KB |
Output is correct |
9 |
Correct |
284 ms |
568656 KB |
Output is correct |
10 |
Correct |
191 ms |
567064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Correct |
1 ms |
6748 KB |
Output is correct |
3 |
Correct |
1 ms |
6812 KB |
Output is correct |
4 |
Correct |
1 ms |
6748 KB |
Output is correct |
5 |
Correct |
1 ms |
6748 KB |
Output is correct |
6 |
Correct |
333 ms |
557956 KB |
Output is correct |
7 |
Correct |
187 ms |
558124 KB |
Output is correct |
8 |
Correct |
262 ms |
602200 KB |
Output is correct |
9 |
Correct |
198 ms |
573140 KB |
Output is correct |
10 |
Correct |
179 ms |
564312 KB |
Output is correct |
11 |
Correct |
169 ms |
563244 KB |
Output is correct |
12 |
Correct |
222 ms |
588080 KB |
Output is correct |
13 |
Correct |
349 ms |
563284 KB |
Output is correct |
14 |
Correct |
284 ms |
568656 KB |
Output is correct |
15 |
Correct |
191 ms |
567064 KB |
Output is correct |
16 |
Correct |
185 ms |
589316 KB |
Output is correct |
17 |
Correct |
249 ms |
687188 KB |
Output is correct |
18 |
Correct |
218 ms |
605464 KB |
Output is correct |
19 |
Correct |
318 ms |
592204 KB |
Output is correct |
20 |
Correct |
192 ms |
605524 KB |
Output is correct |
21 |
Correct |
353 ms |
784960 KB |
Output is correct |
22 |
Correct |
294 ms |
784652 KB |
Output is correct |
23 |
Correct |
426 ms |
784468 KB |
Output is correct |
24 |
Correct |
299 ms |
784616 KB |
Output is correct |
25 |
Correct |
343 ms |
784976 KB |
Output is correct |