Submission #1069626

#TimeUsernameProblemLanguageResultExecution timeMemory
1069626thangdz2k7Cyberland (APIO23_cyberland)C++17
0 / 100
20 ms7256 KiB
#include <bits/stdc++.h> #define db double using namespace std; const db inf = 1e12; 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; for (int loops = 0; loops <= K; ++ loops){ priority_queue <pair <db, int>> qu; for (int u = 0; u < N; ++ u){ if (dp[u] == inf) continue; if (arr[u] == 0) dp[u] = 0.0; if (arr[u] == 2) dp[u] /= mid; qu.push({-dp[u], u}); } while (qu.empty()){ auto [du, u] = qu.top(); qu.pop(); du = -du; if (du != dp[u]) continue; for (int id : adj[u]){ int v = x[id] ^ y[id] ^ u; if (dp[v] > dp[u] + c[id]){ dp[v] = dp[u] + c[id]; qu.push({-dp[v], v}); } } } } return dp[H]; }
#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...