| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 541260 | rainliofficial | Museum (CEOI17_museum) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define f first
#define s second
/**
* The challenge of the problem is to know which edges we want to "backtrack" on (meaning we pass an edge twice).
* It is key that we realize the given graph is a tree, which means we can use tree DP.
*
* Let dp[i][j][0/1] = the min cost to visit j nodes in subtree of i, such that 0 = we don't return back to i, 1 = we return back to i
*/
struct edge{
int to, c;
};
const int MAXN = 10001;
int n, k, x, ss[MAXN], dp[MAXN][MAXN][2], dp2[MAXN][MAXN][2];
vector<edge> arr[MAXN];
void subtreeSize(int at, int par){
ss[at] = 1;
for (edge i : arr[at]){
if (i.to != par){
subtreeSize(i.to, at);
ss[at] += ss[i.to];
}
}
}
void dfs(int at, int par){
// try to "tack on" the answer of the children of at
int currSize = 1;
for (edge i : arr[at]){
if (i.to != par){
dfs(i.to, at);
// combine the new subtree with the existing subtree of at
for (int atSize=1; atSize<=currSize; atSize++){
for (int newSize=1; newSize<=ss[i.to]; newSize++){
dp2[at][atSize + newSize][0] = min({dp2[at][atSize + newSize][0], dp[at][atSize][1] + dp[i.to][newSize][0] + i.c, dp[at][atSize][0] + dp[i.to][newSize][1] + 2*i.c});
dp2[at][atSize + newSize][1] = min(dp2[at][atSize + newSize][1], dp[at][atSize][1] + dp[i.to][newSize][1] + 2*i.c);
}
}
// copy over data
for (int atSize=1; atSize<=currSize; atSize++){
for (int newSize=1; newSize<=ss[i.to]; newSize++){
dp[at][atSize + newSize][0] = min(dp[at][atSize + newSize][0], dp2[at][atSize + newSize][0]);
dp[at][atSize + newSize][1] = min(dp[at][atSize + newSize][1], dp2[at][atSize + newSize][1]);
}
}
for (int atSize=1; atSize<=currSize; atSize++){
for (int newSize=1; newSize<=ss[i.to]; newSize++){
dp2[at][atSize + newSize][0] = dp2[at][atSize + newSize][1] = INT_MAX;
}
}
currSize += ss[i.to];
}
}
}
int main(){
cin.tie(0); ios_base::sync_with_stdio(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
cin >> n >> k >> x;
x--;
for (int i=0; i<n-1; i++){
int a, b, c;
cin >> a >> b >> c;
a--; b--;
arr[a].push_back({b, c});
arr[b].push_back({a, c});
}
for (int i=0; i<MAXN; i++){
for (int j=0; j<MAXN; j++){
if (j > 1){
dp[i][j][0] = dp[i][j][1] = INT_MAX;
}
dp2[i][j][0] = dp2[i][j][1] = INT_MAX;
}
}
subtreeSize(x, -1);
dfs(x, -1);
cout << dp[x][k][0] << "\n";
}