#include "cyberland.h"
#include <bits/stdc++.h>
const int MAX_N = 1e5 + 10;
const int MAX_K = 31;
typedef long double ld;
ld dist[2][MAX_N][MAX_K];
std::vector<std::pair<int, int> > g[MAX_N];
bool used[MAX_N];
void dfs(int x) {
if(used[x]) { return; }
used[x] = true;
for(const auto &it : g[x]) {
dfs(it.first);
}
}
ld pw[MAX_K];
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) {
for(int i = 0; i < N; i ++) {
g[i].resize(0);
used[i] = false;
}
for(int i = 0; i < M; i ++) {
g[x[i]].push_back({y[i], c[i]});
g[y[i]].push_back({x[i], c[i]});
}
dfs(0);
K = std::min(K, MAX_K - 1);
pw[0] = 1;
for(int i = 1; i <= K; i ++) {
pw[i] = (pw[i - 1] * 2.0);
}
for(int i = 0; i < N; i ++) {
for(int j = 0; j <= K; j ++) {
dist[0][i][j] = dist[1][i][j] = 1e18;
}
}
for(int left = K; left >= 0; left --) {
std::priority_queue<std::pair<ld, int> > pq;
for(int i = 0; i < N; i ++) {
if(i == 0) {
dist[0][i][left] = 0;
}
if(dist[0][i][left] < 1e17) {
pq.push({-dist[0][i][left], i});
}
if(dist[1][i][left] < 1e17) {
pq.push({-dist[1][i][left], i + MAX_N});
}
}
while(!pq.empty()) {
auto curr = pq.top(); pq.pop();
curr.first *= -1;
bool used = curr.second / MAX_N;
curr.second %= MAX_N;
if(curr.first > dist[used][curr.second][left]) {
continue;
}
if(curr.second == H) { continue; }
for(const auto &it : g[curr.second]) {
ld new_cost = curr.first + it.second / pw[left];
if(dist[0][it.first][left] > new_cost) {
dist[0][it.first][left] = new_cost;
pq.push({-new_cost, it.first});
}
}
}
for(int i = 0; i < N; i ++) {
if(arr[i] == 2) {
dist[1][i][left - 1] = dist[0][i][left];
} else if(arr[i] == 0) {
if(dist[0][i][left] < 1e17) {
dist[1][i][left - 1] = 0;
}
}
}
}
ld ret = std::min(dist[0][H][0], dist[1][H][0]);
if(ret > 1e17) {
return -1;
}
return ret;
}
