#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
double
solve (int n, int m, int k, int h,
std::vector<int> x, std::vector<int> y, std::vector<int> c,
std::vector<int> arr)
{
vector < vector < pair < int, int > > > adj (n);
for (int i = 0; i < m; ++i)
{
adj[x[i]].push_back ({ c[i], y[i] });
adj[y[i]].push_back ({ c[i], x[i] });
}
priority_queue < pair < ll, int > > q;
q.push ({ 0ll, 0 });
vector < ll > sda (n, -1);
while (q.size ())
{
auto x = q.top ();
q.pop ();
if (sda[x.second] != -1) continue;
sda[x.second] = -x.first;
if (x.second == h) continue;
for (auto &y : adj[x.second])
q.push ({ x.first - y.first, y.second });
}
if (sda[h] == -1) return -1;
set < int > rz;
rz.insert (0);
for (int i = 0; i < n; ++i)
if (arr[i] == 0 && sda[i] > 0)
rz.insert (i);
set < int > rd;
for (int i = 0; i < n; ++i)
if (arr[i] == 2 && sda[i] > 0)
rd.insert (i);
k = min (k, 80);
vector < vector < double > > da (k + 1, vector < double > (n, -1));
double ans = 1e18;
for (ll i = 0; i <= k; ++i)
{
priority_queue < pair < double, int > > pq;
if (!i)
for (auto &x : rz)
pq.push ({ (double) 0, x });
else
for (auto &x : rd)
for (auto &y : adj[x])
pq.push ({ (double) -da[i - 1][x] / 2 - y.first, y.second });
while (pq.size ())
{
auto x = pq.top ();
pq.pop ();
if (da[i][x.second] >= -0.5) continue;
da[i][x.second] = -x.first;
if (x.second == h) continue;
for (auto &y : adj[x.second])
pq.push ({ (double) x.first - y.first, y.second });
}
if (da[i][h] >= -0.5)
ans = min (ans, da[i][h]);
}
return ans;
}
