Submission #1253816

#TimeUsernameProblemLanguageResultExecution timeMemory
1253816anfiCyberland (APIO23_cyberland)C++20
15 / 100
293 ms21404 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second const double inf = 1e30; const double eps = 1e-9; double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { K = min(K, 70); vector<vector<double>> dp(N, vector<double>(K+1, inf)); vector<vector<pair<int, int>>> adj(N); for (int i = 0; i < M; i++) { adj[x[i]].push_back({y[i], c[i]}); adj[y[i]].push_back({x[i], c[i]}); } if (H == 0) { return 0.0; } priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> pq; dp[H][0] = 0.0; pq.push({0.0, H, 0}); while (!pq.empty()) { auto [cost, u, j] = pq.top(); pq.pop(); if (cost - dp[u][j] > eps) { continue; } if (u == 0) { continue; } if (arr[u] == 0) { if (cost < dp[0][j] - eps) { dp[0][j] = cost; pq.push({cost, 0, j}); } } for (auto &[v, w] : adj[u]) { double new_cost1 = cost + w; if (new_cost1 < dp[v][j] - eps) { dp[v][j] = new_cost1; pq.push({new_cost1, v, j}); } if (arr[u] == 2 && j < K) { double new_cost2 = cost + (double)w / 2.0; if (new_cost2 < dp[v][j+1] - eps) { dp[v][j+1] = new_cost2; pq.push({new_cost2, v, j+1}); } } } } double ans = inf; for (int j = 0; j <= K; j++) { if (dp[0][j] < ans) { ans = dp[0][j]; } } if (ans >= inf - 1) { return -1.0; } else { 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...