#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
const int NN = 1e5 + 5, KK = 71 ;
vector<array<int, 2> > g[NN];
bool isreachable[NN];
double dp[NN][KK];
int a[NN];
void dfs(int node, int restricted)
{
isreachable[node] = true;
for(auto [to, wt]: g[node])
{
if(to == restricted)
{
isreachable[restricted] = true;
}
if(to == restricted || isreachable[to]) continue;
dfs(to, restricted);
}
}
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, 70);
for(int i = 0; i < N; i++)
{
a[i] = arr[i];
isreachable[i] = false;
g[i].clear();
for(int j = 0; j <= K; j++)
{
dp[i][j] = 1e18;
}
}
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]});
}
dfs(0, H);
if(!isreachable[H])
{
return -1;
}
priority_queue<pair<double, pair<int, int> > > pq;
dp[0][0] = 0;
pq.push({-dp[0][0], {0, 0}});
for(int i = 1; i < N; i++)
{
if(isreachable[i] && arr[i] == 0)
{
dp[i][0] = 0;
pq.push({-dp[i][0], {i, 0}});
}
}
while(!pq.empty())
{
auto [dis, l] = pq.top();
auto [node, k] = l;
// cout << "dis = " << dis << ", node = " << node << ", k = " << k << "\n";
pq.pop();
dis = -dis;
if(dp[node][k] < dis)
{
continue;
}
for(auto [to, wt]: g[node])
{
if(dp[to][k] > dp[node][k] + wt)
{
dp[to][k] = dp[node][k] + (long long)wt;
if(to != H)
{
pq.push({-dp[to][k], {to, k}});
}
}
// cout << "a[to] = " << a[to] << "k = " << k << ", K = " << K << ", dp[to][k + 1] = " << dp[to][k + 1] << "\n";
if(a[to] == 2 && k != K && dp[to][k + 1] > (dp[node][k] + (double)wt) / 2.0)
{
dp[to][k + 1] = (dp[node][k] + wt) / 2.0;
if(to != H)
{
pq.push({-dp[to][k + 1], {to, k + 1}});
}
}
}
}
double ans = 1e18;
for(int i = 0; i <= K; i++)
{
ans = min(ans, dp[H][i]);
}
return ans;
}
