| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 951997 |
2024-03-23T03:33:35 Z |
vjudge1 |
Museum (CEOI17_museum) |
C++17 |
|
453 ms |
1064 KB |
#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
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
453 ms |
1064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
453 ms |
1064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
