제출 #561157

#제출 시각아이디문제언어결과실행 시간메모리
561157proma경주 (Race) (IOI11_race)C++17
9 / 100
195 ms48848 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; const int N = 1e5+5; const int INF = 1e9; vector <pair <int, int>> g[N]; int ans, k, used[N], dp[N][105]; void dfs(int v) { used[v] = 1; for (int i = 1; i <= k; i ++) dp[v][i] = INF; for (auto i: g[v]) { if (!used[i.first]) { dfs(i.first); for (int j = 1; j <= k; j ++) { if (j - i.second >= 0) { dp[v][j] = min(dp[v][j], dp[i.first][j-i.second] + 1); } } } } } int best_path(int N, int K, int H[][2], int L[]) { k = K; for (int i = 0; i < N; i ++) { g[H[i][0]].push_back({H[i][1], L[i]}); g[H[i][1]].push_back({H[i][0], L[i]}); } int ans = INF; vector <int> nodes = {0, N/2, N-1}; for (auto v: nodes) { memset(used, 0, sizeof(used)); dfs(v); for (int i = 0; i < N; i ++) { ans = min(ans, dp[i][k]); } } if (ans == INF) ans = -1; return 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...