#include "cyberland.h"
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <iterator>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using std::array;
using std::pair;
using std::tuple;
using std::vector;
struct union_find {
explicit union_find(int n) : data(n, -1) {}
int find(int u) { return data[u] < 0 ? u : data[u] = find(data[u]); }
bool same(int x, int y) { return find(x) == find(y); }
void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (data[x] > data[y]) std::swap(x, y);
data[x] += data[y];
data[y] = x;
}
private:
vector<int> data;
};
double solve(int N, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> A) {
constexpr int MaxK = 70;
K = std::min(K, MaxK - 1);
union_find dsu(N);
vector<int> Z(M);
vector<vector<int>> G(N);
for (int i = 0; i < M; ++i) {
Z[i] = X[i] ^ Y[i];
G[X[i]].push_back(i);
G[Y[i]].push_back(i);
if (X[i] != H && Y[i] != H) dsu.merge(X[i], Y[i]);
}
array<double, MaxK> pow;
pow[0] = 1;
for (int i = 1; i < MaxK; ++i) {
pow[i] = pow[i - 1] * 0.5;
}
vector<array<double, MaxK>> dist(N);
for (auto& a : dist) a.fill(1e16);
struct Info {
int u, k;
double d;
bool operator<(const Info& t) const { return d > t.d; }
};
std::priority_queue<Info> heap;
const auto push = [&](int u, int k, double d) {
if (dist[u][k] > d) {
dist[u][k] = d;
heap.push({u, k, d});
}
};
A[0] = 0;
push(H, K, 0);
while (!heap.empty()) {
const auto [u, k, d] = heap.top();
heap.pop();
if (dist[u][k] < d) continue;
if (A[u] == 0) return d;
for (const int e : G[u]) {
const int v = Z[e] ^ u;
if (!dsu.same(0, v)) continue;
push(v, k, d + C[e] * pow[K - k]);
if (A[u] == 2 && k > 0) push(v, k - 1, d + C[e] * pow[K - k + 1]);
}
}
return -1;
}
