Submission #951997

#	Time	Username	Problem	Language	Result	Execution time	Memory
951997		vjudge1	Museum (CEOI17_museum)	C++17	0 / 100	453 ms	1064 KiB

museum

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e4 + 2;
int n, k, x;
//int dp[N][N][2], son[N];
vector<pii> g[N];
int vis[N], tot, ans = 0x3f3f3f3f;
//void dfs(int u, int fa) {
//	son[u] = 1;
//	dp[u][0][0] = dp[u][0][1] = 0;
//	for (pii f : g[u]) {
//		int v = f.first, w = f.second;
//		if (v == fa) continue;
//		dfs(v, u);
//		son[u] += son[v];
//		for (int i = min(son[u], k); i >= 0; i--) {
//			for (int j = 0; j <= min(son[v], i - 2); j++) {
//				dp[u][i][0] = min(dp[u][i][0], dp[u][i - j - 1][0] + dp[v][j][0] + w * 2);
//				dp[u][i][1] = min(dp[u][i][1], dp[u][i - j - 1][0] + dp[v][j][1] + w);
//				dp[u][i][1] = min(dp[u][i][1], dp[u][i - j - 2][1] + dp[v][j][1] + w * 2);
//			}
//			dp[u][i][1] = min(dp[u][i][1], dp[v][0][0] + dp[u][i - 1][1]);
//		}
//	}
//}
void baoli(int u, int t, int sum) {
	tot++;
	if (t >= k) {
		ans = min(ans, sum);
		return ;
	}
	if (tot >= 7e7) return ;
	for (pii f : g[u]) {
		int v = f.first, w = f.second;
		if (vis[v] == 2) continue;
		int s;
		if (vis[v] == 0) s = 1;
		if (vis[v] == 0) vis[v] = 1;
		else vis[v] = 2;
		baoli(u, t + s, sum + w);
		vis[v] = 0;
	}
}
int main() {
//	freopen("museum.in", "r", stdin);
//	freopen("museum.out", "w", stdout);
	scanf("%d%d%d", &n, &k, &x);
	for (int i = 1; i < n; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	if (k == 1) return ! printf("0");
//	memset(dp, 0x3f, sizeof dp);
	vis[1] = 1;
//	dfs(x, -1);
	baoli(x, 1, 0);
//	for (int i = 1; i <= n; i++) {
//		for (int j = 0; j <= k; j++) {
//			if (dp[i][j][0] == 0x3f3f3f3f) dp[i][j][0] = -1;
//			if (dp[i][j][1] == 0x3f3f3f3f) dp[i][j][1] = -1;
//			printf("(%2d,%2d) ", dp[i][j][0], dp[i][j][1]);
//		}
//		printf("\n");
//	} 
	printf("%d\n", ans);
}

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d%d%d", &n, &k, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
museum.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d%d%d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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