# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
952111 | 2024-03-23T06:07:22 Z | vjudge1 | Museum (CEOI17_museum) | C++17 | 63 ms | 217684 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]; void dfs(int u, int fa) { son[u] = 1; dp[u][1][0] = dp[u][1][1] = 0; for (pii f : g[u]) { int v = f.first, w = f.second; if (v == fa) continue; dfs(v, u); for (int i = min(son[u] + 3, k); i >= 0; i--) { for (int j = 0; j <= min(son[v] + 3, i); j++) { dp[u][i][0] = min(dp[u][i][0], dp[u][i - j][0] + dp[v][j][0] + w * 2); dp[u][i][1] = min(dp[u][i][1], dp[u][i - j][0] + dp[v][j][1] + w); dp[u][i][1] = min(dp[u][i][1], dp[u][i - j][1] + dp[v][j][0] + w * 2); } } son[u] += son[v]; } } int main() { 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}); } for (int i = 1; i <= n; i++) { for (int j = 0; j <= k; j++) { dp[i][j][0] = dp[i][j][1] = 0x3f3f3f3f; } } dfs(x, -1); printf("%d\n", min(dp[x][k][0], dp[x][k][1])); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2656 KB | Output is correct |
2 | Incorrect | 1 ms | 2648 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 63 ms | 217684 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 63 ms | 217684 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2656 KB | Output is correct |
2 | Incorrect | 1 ms | 2648 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |