Submission #1253828

#TimeUsernameProblemLanguageResultExecution timeMemory
1253828anfiCyberland (APIO23_cyberland)C++20
15 / 100
668 ms25444 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) { K = min(K, 100); 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]}); } vector dp(N, vector<double>(K+1, INF)); priority_queue< tuple<double,int,int>, vector<tuple<double,int,int>>, greater<tuple<double,int,int>> > pq; dp[0][0] = 0; pq.push({0, 0, 0}); while(!pq.empty()){ auto [dist, u, used] = pq.top(); pq.pop(); if(dist > dp[u][used]) continue; for(auto [v, w] : adj[u]){ double nd = dist + w; if(nd < dp[v][used]){ dp[v][used] = nd; pq.push({nd, v, used}); } } } for(int i = 0; i < N; i++){ if(arr[i] == 0 && dp[i][0] > 0){ dp[i][0] = 0; pq.push({0, i, 0}); } } while(!pq.empty()){ auto [dist, u, used] = pq.top(); pq.pop(); if(dist > dp[u][used]) continue; for(auto [v, w] : adj[u]){ if(dist + w < dp[v][used]){ dp[v][used] = dist + w; pq.push({dp[v][used], v, used}); } if(arr[u] == 2 && used < K){ double cd = dist + w/2.0; if(cd < dp[v][used+1]){ dp[v][used+1] = cd; pq.push({cd, v, used+1}); } } } if(u == H && arr[H]==2 && used < K){ if(dist/2.0 < dp[H][used+1]){ dp[H][used+1] = dist/2.0; pq.push({dp[H][used+1], H, used+1}); } } } double ans = INF; for(int d = 0; d <= K; d++) ans = min(ans, dp[H][d]); 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...