#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using key = pair<double, int>;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
K = min(K, 100);
vector<vector<pair<int, int>>> g(N);
for (int i = 0; i < M; ++i) {
g[x[i]].emplace_back(y[i], c[i]);
g[y[i]].emplace_back(x[i], c[i]);
}
vector<bool> reachable(N, 0);
function<void(int)> dfs = [&](int v) {
if (reachable[v]) return;
reachable[v] = true;
if (v == H) return;
for (auto [u, _] : g[v]) {
dfs(u);
}
};
dfs(0);
priority_queue<key, vector<key>, greater<key>> pq;
vector<vector<double>> dp(N, vector<double> (K + 2, -1));
for (int k = 0; k <= K; ++k) {
for (int i = 0; i < N; ++i) {
if (i == 0 || (reachable[i] && arr[i] == 0)) {
dp[i][k] = 0;
}
if (dp[i][k] != -1) {
pq.emplace(dp[i][k], i);
}
}
while (!pq.empty()) {
auto [cost, v] = pq.top();
pq.pop();
if (cost != dp[v][k] || v == H) {
continue;
}
for (auto [u, w] : g[v]) {
double nc = cost + w;
if (dp[u][k] == -1 || nc < dp[u][k]) {
dp[u][k] = nc;
pq.emplace(dp[u][k], u);
}
if (arr[u] == 2) {
nc = nc / 2.0;
if (dp[u][k + 1] == -1 || nc < dp[u][k + 1]) {
dp[u][k + 1] = nc;
}
}
}
}
}
double ans = -1;
for (int i = 0; i <= K; ++i) {
if (dp[H][i] != -1 && (ans == -1 || ans > dp[H][i])) {
ans = dp[H][i];
}
}
if (reachable[H]) assert(ans != -1);
else assert(ans == -1);
return ans;
}
