#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll LL_INF = (ll)1e18+1;
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<vector<pair<int, int>>> adj(N);
for(int i = 0; i < M; ++i) {
adj[x[i]].emplace_back(y[i], c[i]);
adj[y[i]].emplace_back(x[i], c[i]);
}
arr[0] = -1; // -1 denotes all startpoints i.e. 0 and all arr[0]s reachable from 0
queue<int> bfs; bfs.push(0);
vector<bool> visited(N);
while(!bfs.empty()) {
int u = bfs.front(); bfs.pop();
if(visited[u]) continue;
visited[u] = true;
if(arr[u] == 0) arr[0] = -1;
if(u == H) continue; // we can't move from H
for(auto [v, c]: adj[u]) bfs.push(v);
}
vector<double> dist(N, DBL_MAX);
// (d, u, k) where k is number of times halved
priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> dijkstra;
dijkstra.emplace(0.0, H, 0);
double min_dist = DBL_MAX;
// for arr[u] = 2, we greedily apply halving (as much as we can as early as we can)
// moving across edge (u, v, c) takes time only c/(2^k);
while(!dijkstra.empty()) {
auto [d, u, k] = dijkstra.top();
dijkstra.pop();
if(d >= dist[u]) continue;
dist[u] = d;
if(arr[u] == 2 && k < K) ++k; // apply superpower!
else if(arr[u] == -1) {
min_dist = min(min_dist, d);
continue; // you'd never have returned to the start, as distance is nondecreasing
// so path will always start from these nodes and never pass through
}
for(auto [v, cv]: adj[u]) {
dijkstra.emplace(d + (double)cv/(1ll << k), v, k);
}
}
if(min_dist == DBL_MAX) return -1;
return min_dist;
}
