# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1253920 | anfi | Cyberland (APIO23_cyberland) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const double inf = 1e18;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
double ans = 1e18;
K = min(K, 100);
vector<pair<int,int>> adj[N];
vector<int> dp(N, inf), tmp(N, 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]});
}
priority_queue<pair<double, int>> pq;
dp[0] = 0.0;
while(!pq.empty()){
auto [c, u] = pq.top(); pq.pop();
if(c > dp[u]) continue;
for(auto &[v, w] : adj[u]){
double cost = c+w;
if(dp[v] > cost){
dp[v] = cost;
pq.push({dp[v], v});
}
if(a[u] == 2 && pos < K){
double co = (c+w)/2.0;
if(dp[v] > co){
dp[v] = co;
pq.push({co, v});
}
}
}
}
for(int i = 0; i <= K; i++) ans = min(ans, dp[H][i]);
return (ans >= inf/2 ? -1.0 : }