#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, _] : 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);
if (!vis[h]) {
return -1;
}
k = min(k, 70);
using node = array<double, 3>;
priority_queue<node, vector<node>, greater<node>> q;
vector<vector<double>> dp(n, vector<double>(k + 1, inf));
for (int i = 0; i < n; i++) {
if (i == 0 || (arr[i] == 0 && vis[i])) {
ranges::fill(dp[i], 0);
q.push({0, (double)i, 0});
}
}
while (!q.empty()) {
auto [x, i, j] = q.top();
q.pop();
if (dp[i][j] < x || i == h) continue;
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});
}
if (arr[v] == 2 && j < k && (x + w) / 2 < dp[v][j + 1]) {
dp[v][j + 1] = (x + w) / 2;
q.push({(x + w) / 2, v, j + 1});
}
}
}
return ranges::min(dp[h]);
}
