#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) { K = min(K, 61); vector<pair<int, double>> adj[N + 1]; vector<vector<double>> dp(N + 1, vector<double>(K + 1, inf)); priority_queue<tuple<double,int,int>> pq; for(int i = 0; i < M; ++i){ adj[x[i]].push_back({y[i], (double) c[i] * 1.00}); adj[y[i]].push_back({x[i], (double) c[i] * 1.00}); } dp[0][K] = 0, pq.push({0.0, 0, -K}); while(!pq.empty()){ auto [dist, node, rem] = pq.top(); dist = -dist, rem = -rem; pq.pop(); if(dist > dp[node][rem]) continue; if(node == H) continue; double base = dist; if(arr[node] == 0) base = 0; for(auto [v, w] : adj[node]){ if(dp[v][rem] > base + w){ dp[v][rem] = base + w; pq.push({-dp[v][rem], v, -rem}); } if(arr[node] == 2 && rem > 0){ if(dp[v][rem-1] > base / 2 + w){ dp[v][rem-1] = base / 2 + w; pq.push({-dp[v][rem-1], v, 1 - rem}); } } } } double ans = inf; for(int i = 0; i <= K; ++i) ans = min(ans, dp[H][i]); return ((ans >= inf || ans <= 0) ? -1 : ans); }