제출 #1004894

#제출 시각아이디문제언어결과실행 시간메모리
1004894cpdreamer경주 (Race) (IOI11_race)C++14
0 / 100
1 ms4444 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define P pair<int, int> #define V vector #define F first #define S second #define pb push_back const int INF = 1e9; int dp[(int)3e5][101]; void dfs(int n, int p, V<P> tree[], int k) { dp[n][0] = 0; // Starting point, no steps taken, zero distance for (auto u : tree[n]) { if (u.F == p) continue; dfs(u.F, n, tree, k); for (int i = k; i >= 0; --i) { if (dp[n][i] == INF) continue; for (int j = 1; j + i <= k; ++j) { if (dp[u.F][j] != INF) { dp[n][i + j] = min(dp[n][i + j], dp[n][i] + dp[u.F][j] + 1); } } } } } int best_path(int N, int K, int H[][2], int L[]) { for (int i = 0; i < N; ++i) for (int j = 0; j <= K; ++j) dp[i][j] = INF; V<P> tree[N]; for (int i = 0; i < N - 1; ++i) { tree[H[i][0]].pb({H[i][1], L[i]}); tree[H[i][1]].pb({H[i][0], L[i]}); } dfs(0, -1, tree, K); int ans = INF; for (int i = 0; i < N; ++i) { ans = min(ans, dp[i][K]); } return (ans == INF) ? -1 : ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...