#include <bits/stdc++.h> #include "cyberland.h" using namespace std; const double inf = 1e18; double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) { vector<pair<int, double>> adj[N + 1]; for(int i = 0; i < M; ++i){ adj[x[i]].push_back({y[i], (double) c[i]}); adj[y[i]].push_back({x[i], (double) c[i]}); } vector<vector<double>> dp(N + 1, vector<double>(K + 1, inf)); priority_queue<tuple<int, int, int>> pq; pq.push({0, -K, 0}); dp[0][K] = 0; while(pq.size()){ auto [dist, rem, node] = pq.top(); pq.pop(); dist = -dist, rem = -rem; if(node == H) continue; if(arr[node] == 0) dist = 0; if(dp[node][rem] < dist) continue; for(auto [v, w] : adj[node]){ if(dp[v][rem] > dist + w){ dp[v][rem] = dist + w; pq.push({-dp[v][rem], -rem, v}); } if(arr[node] == 2 && rem){ if(dp[v][rem - 1] > (dist / 2.0) + w){ dp[v][rem - 1] = (dist / 2.0) + w; pq.push({-dp[v][rem - 1], -(rem - 1), v}); } } } } double ans = inf; for(int i = 0; i <= K; ++i) ans = min(ans, dp[H][i]); return ((ans >= inf || ans <= 0) ? -1 : ans); }