Submission #1069653

#TimeUsernameProblemLanguageResultExecution timeMemory
1069653thangdz2k7Cyberland (APIO23_cyberland)C++17
15 / 100
249 ms7808 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; db ans = inf; 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.size()){ 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}); } } } ans = min(ans, dp[H]); } if (ans == inf) return -1; return ans; } // //int main(){ // int N, M, K; cin >> N >> M >> K; // int H; cin >> H; // vector <int> arr(N); for (int i = 0; i < N; ++ i) cin >> arr[i]; // vector <int> x(M), y(M), z(M); for (int i = 0; i < M; ++ i) cin >> x[i] >> y[i] >> z[i]; // cout << fixed << setprecision(10) << solve(N, M, K, H, x, y, z, arr); //}
#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...