#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] * 1.00}); adj[y[i]].push_back({x[i], (double) c[i] * 1.00}); } K = min(K, 66); vector<vector<double>> dp(N + 1, vector<double>(K + 1, inf)); priority_queue< tuple<double,int,int>, vector<tuple<double,int,int>>, greater<> > pq; dp[0][K] = 0; pq.push({0.0, 0, K}); while(!pq.empty()){ auto [dist, node, rem] = pq.top(); 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, rem-1}); } } } } double ans = inf; for(int i = 0; i <= K; ++i) ans = min(ans, dp[H][i]); return ((ans >= inf || ans <= 0) ? -1 : ans); }