Submission #1253826

#TimeUsernameProblemLanguageResultExecution timeMemory
1253826anfiCyberland (APIO23_cyberland)C++20
15 / 100
529 ms25780 KiB
#include<bits/stdc++.h> using namespace std; #define fi first #define se second const double inf = 1e30; double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){ double ans = 1e30; K = min(K, 100); vector<pair<int,int>> adj[N]; vector<vector<double>> dp(N, vector<double>(K+1, inf)); 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]}); } vector<int> a = arr; priority_queue<tuple<double,int,int>, vector<tuple<double, int, int>>, greater<tuple<double,int,int>>> pq; dp[0][0] = 0.0; pq.push({0.0, 0,0}); while(!pq.empty()){ auto [c, u, pos] = pq.top(); pq.pop(); if(c > dp[u][pos]) continue; for(auto &[v, w] : adj[u]){ double cost = c+w; if(dp[v][pos] > cost){ dp[v][pos] = cost; pq.push({cost, v, pos}); } } } for(int i = 0; i < N; i++){ if(a[i] == 0 && dp[i][0] > 0){ dp[i][0] = 0; pq.push({0.0, i, 0}); } } if (dp[0][0] == 0.0) { pq.push({0.0, 0, 0}); } while(!pq.empty()){ auto [c, u, pos] = pq.top(); pq.pop(); if(c > dp[u][pos]) continue; for(auto &[v, w] : adj[u]){ double cost = c+w; if(dp[v][pos] > cost){ dp[v][pos] = cost; pq.push({cost, v, pos}); } if(a[u] == 2 && pos < K){ double co = c+w/2.0; if(dp[v][pos+1] > co){ dp[v][pos+1] = co; pq.push({co, v, pos+1}); } } } if(u == H && a[H] == 2 && pos < K){ if(dp[H][pos+1] > c/2.0){ dp[H][pos+1] = c/2.0; pq.push({dp[H][pos+1], H, pos+1}); } } } for(int i = 0; i <= K; i++) ans = min(ans, dp[H][i]); return (ans >= inf/2 ? -1.0 : 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...