#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9
// #define fisier
using namespace std;
typedef long long ll;
int add(int a, int b)
{
ll x = a+b;
if(x >= mod)
x -= mod;
if(x < 0)
x += mod;
return x;
}
ll mul(ll a, ll b)
{
return (a*b) % mod;
}
ll pw(ll a, ll b)
{
ll ans = 1;
while(b)
{
if(b & 1)
ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
int n, k, x;
ll dp[10002][10002];
int xtr[10002][10002];
bool is[10002][10002];
vector<pair<int, int> >v[10002];
ll dp2[2][10002];
int xtr2[2][10002];
bool viz2[2][10002];
int sts[10002];
void dfs(int dad, int nod, int cost)
{
sts[nod] = 1;
for(int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i].fi;
if(vecin == dad)
continue;
dfs(nod, vecin, v[nod][i].se);
}
memset(dp2, 0, sizeof(dp2));
memset(viz2, 0, sizeof(viz2));
memset(xtr2, 0, sizeof(xtr2));
viz2[0][1] = 1;
for(int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i].fi;
if(vecin == dad)
continue;
sts[nod] += sts[vecin];
int edcost = v[nod][i].se;
for(int j = sts[nod]; j >= 0; --j)
for(int trb = 0; trb <= 1; ++trb)
for(int sz = 1; sz <= min(j, sts[vecin]); ++sz)
{
if(!viz2[trb][j - sz])
continue;
if(!viz2[trb][j] || dp2[trb][j - sz] + dp[vecin][sz] + xtr[vecin][sz] + edcost < dp2[trb][j])
{
dp2[trb][j] = dp2[trb][j - sz] + dp[vecin][sz] + xtr[vecin][sz] + edcost;
viz2[trb][j] = 1;
xtr2[trb][j] = xtr2[trb][j - sz];
}
else
if(dp2[trb][j - sz] + dp[vecin][sz] + 2 * xtr[vecin][sz] == dp2[trb][j])
xtr2[trb][j] = min(xtr2[trb][j], xtr2[trb][j - sz]);
if(trb == 0)
{
if(!viz2[1][j] || dp2[0][j - sz] + dp[vecin][sz] + edcost < dp2[1][j])
{
dp2[1][j] = dp2[0][j - sz] + dp[vecin][sz] + edcost;
viz2[1][j] = 1;
xtr2[1][j] = xtr[vecin][sz];
}
else
if(dp2[0][j - sz] + dp[vecin][sz] + edcost == dp2[1][j])
xtr2[1][j] = min(xtr2[1][j], xtr[vecin][sz]);
}
}
}
is[nod][1] = 1;
dp[nod][1] = 0;
for(int i = 2; i <= sts[nod]; ++i)
if(viz2[1][i])
{
is[nod][i] = 1;
dp[nod][i] = dp2[1][i];
xtr[nod][i] = xtr2[1][i];
}
for(int i = 1; i <= sts[nod]; ++i)
xtr[nod][i] += cost;
/*
cout << nod << '\n';
for(int i = 1; i <= sts[nod]; ++i)
cout << dp[nod][i] << " ";
cout << '\n';
for(int i = 1; i <= sts[nod]; ++i)
cout << xtr[nod][i] << " ";
cout << '\n';
*/
}
int main()
{
#ifdef fisier
ifstream f("input.in");
ofstream g("output.out");
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k >> x;
for(int i = 1; i < n; ++i)
{
int a, b, c;
cin >> a >> b >> c;
v[a].pb({b, c});
v[b].pb({a, c});
}
dfs(0, x, 0);
cout << dp[x][k] << '\n';
return 0;
}
Compilation message
museum.cpp: In function 'void dfs(int, int, int)':
museum.cpp:60:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); ++i)
~~^~~~~~~~~~~~~~~
museum.cpp:71:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); ++i)
~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1016 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1467 ms |
126708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1467 ms |
126708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1016 KB |
Output is correct |
| 6 |
Incorrect |
1467 ms |
126708 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
