#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "task"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7;
vector<pair<int,int>> a[10005];
vector<ll> f[10005];
vector<ll> f2[10005];
int n,m,st;
void dfs(int u,int par)
{
f[u]=f2[u]={0,0};
for(auto i:a[u])
{
if(i.fi!=par)
{
dfs(i.fi,u);
int v=i.fi;
vector<ll> inter(min((ll)(m+1),(ll)(f[u].size()+f[v].size()-1)),MAX);
vector<ll> inter2(min((ll)(m+1),(ll)(f2[u].size()+f2[v].size()-1)),MAX);
inter2[0]=inter[0]=inter[1]=inter2[1]=0;
for(int j=1;j<f[u].size();j++)
{
for(int k=0;k<f[v].size();k++)
{
if(j+k>m+1) break;
inter[j+k]=min(inter[j+k],f[u][j]+f[v][k]+i.se*2*(k!=0));
inter2[j+k]=min(inter2[j+k],min(f[v][k],f2[v][k])+f[u][j]+i.se*(k!=0));
// if(u==3 and v==7 and j+k==2) cout<<j<<" "<<k<<" "<<f[u][j]+f[v][k]+i.se*2*(k!=0)<<endl;
inter2[j+k]=min(inter2[j+k],f2[u][j]+f[v][k]+i.se*2*(k!=0));
}
}
// if(u==3 and v==7 )
// {
// for(int j=0;j<inter.size();j++) cout<<j<<" "<<inter[j]<<endl;
// cout<<inter.size();
// }
swap(f[u],inter);
swap(f2[u],inter2);
}
}
}
int main(){
// #ifndef ONLINE_JUDGE
// freopen (task".inp", "r", stdin);
// freopen (task".out", "w", stdout);
// #endif
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>st;
for(int i=1;i<=n-1;i++)
{
int x,y,z;
cin>>x>>y>>z;
a[x].push_back({y,z});
a[y].push_back({x,z});
}
dfs(st,0);
// cout<<f2[7][5]<<endl;
// cout<<st<<" "<<m;
cout<<min(f[st][m],f2[st][m]);
}
/*
*/
Compilation message
museum.cpp: In function 'void dfs(int, int)':
museum.cpp:30:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int j=1;j<f[u].size();j++)
| ~^~~~~~~~~~~~
museum.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int k=0;k<f[v].size();k++)
| ~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
1028 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
3216 KB |
Output is correct |
2 |
Correct |
9 ms |
3156 KB |
Output is correct |
3 |
Correct |
12 ms |
8460 KB |
Output is correct |
4 |
Correct |
12 ms |
5972 KB |
Output is correct |
5 |
Correct |
10 ms |
4820 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
3216 KB |
Output is correct |
2 |
Correct |
9 ms |
3156 KB |
Output is correct |
3 |
Correct |
12 ms |
8460 KB |
Output is correct |
4 |
Correct |
12 ms |
5972 KB |
Output is correct |
5 |
Correct |
10 ms |
4820 KB |
Output is correct |
6 |
Correct |
14 ms |
2748 KB |
Output is correct |
7 |
Correct |
12 ms |
7944 KB |
Output is correct |
8 |
Correct |
13 ms |
2232 KB |
Output is correct |
9 |
Correct |
14 ms |
2256 KB |
Output is correct |
10 |
Correct |
18 ms |
2388 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
1028 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
12 ms |
3216 KB |
Output is correct |
7 |
Correct |
9 ms |
3156 KB |
Output is correct |
8 |
Correct |
12 ms |
8460 KB |
Output is correct |
9 |
Correct |
12 ms |
5972 KB |
Output is correct |
10 |
Correct |
10 ms |
4820 KB |
Output is correct |
11 |
Correct |
14 ms |
2748 KB |
Output is correct |
12 |
Correct |
12 ms |
7944 KB |
Output is correct |
13 |
Correct |
13 ms |
2232 KB |
Output is correct |
14 |
Correct |
14 ms |
2256 KB |
Output is correct |
15 |
Correct |
18 ms |
2388 KB |
Output is correct |
16 |
Correct |
39 ms |
3992 KB |
Output is correct |
17 |
Correct |
130 ms |
5212 KB |
Output is correct |
18 |
Correct |
52 ms |
30840 KB |
Output is correct |
19 |
Correct |
81 ms |
2360 KB |
Output is correct |
20 |
Correct |
40 ms |
3008 KB |
Output is correct |
21 |
Correct |
238 ms |
169160 KB |
Output is correct |
22 |
Correct |
169 ms |
5700 KB |
Output is correct |
23 |
Correct |
349 ms |
2836 KB |
Output is correct |
24 |
Correct |
175 ms |
4204 KB |
Output is correct |
25 |
Correct |
316 ms |
294712 KB |
Output is correct |