Submission #155709

#	Time	Username	Problem	Language	Result	Execution time	Memory
155709		Fischer	Museum (CEOI17_museum)	C++14	80 / 100	3034 ms	44836 KiB

museum

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 2;
struct Node {
	int v, w;
};
vector<Node> g[maxn];
int n, k, x;
int sz[maxn];
int memo[maxn][maxn][2];

void dfs(int x, int p) {
	sz[x] = 1;
	for (auto node : g[x]) {
		if (node.v == p) continue;
		dfs(node.v, x);
		sz[x] += sz[node.v];
	}
	for (int i = 2; i <= min(sz[x], k); ++i) {
		memo[x][i][0] = memo[x][i][1] = 1e9;
	}
	for (auto node : g[x]) {
		if (node.v == p) continue;
		for (int i = min(sz[x], k); i >= 2; --i) {
			for (int j = 1; j <= min(sz[node.v], i-1); ++j) {
				memo[x][i][1] = min(memo[x][i][1],
					min(
						memo[x][i-j][1] + memo[node.v][j][0] + 2*node.w,
						memo[x][i-j][0] + memo[node.v][j][1] + node.w
					));
				memo[x][i][0] = min(memo[x][i][0], 
					memo[x][i-j][0] + memo[node.v][j][0] + 2*node.w);
			}
		}
	}
}

int main() {
	cin >> n >> k >> x;
	for (int i = 1; i <= n-1; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}
	dfs(x, 0);
	cout << memo[x][k][1] << endl;
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 0 / 20