#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
constexpr double inf = 1e18;
int t;
vector<bool> vis;
vector<vector<pair<double, double>>> g;
void go(int u) {
vis[u] = true;
if (u == t) return;
for (auto [v, w] : g[u]) {
if (!vis[v]) {
go(v);
}
}
}
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
t = h;
g.assign(n, {});
vis.assign(n, 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]});
}
go(0);
k = min(k, 70);
vector<double> pw(k + 1, 1);
for (int i = 1; i <= k; i++) {
pw[i] = pw[i - 1] / 2;
}
using node = tuple<double, int, int>;
priority_queue<node, vector<node>, greater<node>> q;
vector<vector<double>> dp(n, vector<double>(k + 1, inf));
ranges::fill(dp[h], 0);
q.push({0, h, 0});
arr[0] = 0;
while (!q.empty()) {
auto [x, i, j] = q.top();
q.pop();
if (dp[i][j] < x) {
continue;
}
if (arr[i] == 0) {
return x;
}
for (auto [v, w] : g[i]) {
if (!vis[v]) continue;
if (x + w < dp[v][j]) {
dp[v][j] = x + w;
q.push({x + w, v, j});
}
double val = x + w * pw[j + 1];
if (arr[v] == 2 && j < k && val < dp[v][j + 1]) {
dp[v][j + 1] = val;
q.push({val, v, j + 1});
}
}
}
return -1;
}
