#include <bits/stdc++.h>
using namespace std;
const int k = 75;
double solve(
int N, int M, int K, int H,
vector<int> x,
vector<int> y,
vector<int> c,
vector<int> arr
) {
const double INF = 1e18;
vector<vector<pair<int,double>>> g(N);
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]});
}
vector<vector<double>> dp(k, vector<double>(N, INF));
priority_queue<
pair<double, pair<int,int>>,
vector<pair<double, pair<int,int>>>,
greater<>
> pq;
dp[0][0] = 0;
pq.push({0, {0, 0}});
while (!pq.empty()) {
auto [dist, st] = pq.top();
pq.pop();
int v = st.first;
int used = st.second;
if (used >= k) continue;
if (dp[used][v] != dist) continue;
// ❗ КЛЮЧЕВОЕ ИСПРАВЛЕНИЕ
if (v == H) continue;
for (auto [u, w] : g[v]) {
double base = dist + w;
// 1) ничего не делать
if (dp[used][u] > base) {
dp[used][u] = base;
pq.push({base, {u, used}});
}
// 2) обнуление
if (arr[u] == 0) {
if (dp[used][u] > 0) {
dp[used][u] = 0;
pq.push({0, {u, used}});
}
}
// 3) деление на 2
if (arr[u] == 2 && used < K) {
double half = base * 0.5;
if (dp[used + 1][u] > half) {
dp[used + 1][u] = half;
pq.push({half, {u, used + 1}});
}
}
}
}
double ans = INF;
for (int i = 0; i < k; i++) {
ans = min(ans, dp[i][H]);
}
if (ans >= INF / 2) return -1;
return ans;
}
