Submission #1069703

#TimeUsernameProblemLanguageResultExecution timeMemory
1069703thangdz2k7Cyberland (APIO23_cyberland)C++17
68 / 100
352 ms10588 KiB
#include <bits/stdc++.h> #define db double using namespace std; const db inf = 1e18; const db mid = 2.0; db solve(int N, int M, int K, int H, vector <int> x, vector <int> y, vector <int> c, vector <int> arr){ K = min(K, 100); vector <vector <int>> adj(N); for (int i = 0; i < M; ++ i) adj[x[i]].push_back(i), adj[y[i]].push_back(i); vector <db> dp(N, inf); dp[0] = 0.0; db ans = inf; for (int loops = 0; loops <= K; ++ loops){ priority_queue <pair <db, int>> qu; vector <db> rd(N, inf); for (int u = 0; u < N; ++ u){ if (dp[u] == inf || (u > 0 && arr[u] == 1)) continue; if (arr[u] == 0) rd[u] = 0.0; qu.push({-dp[u] / mid, u}); } while (qu.size()){ auto [du, u] = qu.top(); qu.pop(); du = -du; if (u == H) continue; for (int id : adj[u]){ int v = x[id] ^ y[id] ^ u; if (rd[v] > du + c[id]){ rd[v] = du + c[id]; qu.push({-rd[v], v}); } } } if (!loops && rd[H] == inf) break; dp = rd; ans = min(ans, dp[H]); } if (ans == inf) return -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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...