#include <bits/stdc++.h>
#include "cyberland.h"
#define TASK "aksdjasd"
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define all(C) C.begin(), C.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int INT_LIM = 2147483647;
const ll LL_LIM = 9223372036854775807;
template <typename X> bool minimize(X &x, const X &y) {if (x>y){x = y; return true;}return false;}
template <typename X> bool maximize(X &x, const X &y) {if (x<y){x = y; return true;}return false;}
///------------------------------------------///
struct DSU{
int par[100005];
void init(int n)
{
FOR(i, 1, n) par[i] = i;
}
int get(int u)
{
return (par[u]==u)?u:par[u] = get(par[u]);
}
bool merge(int u, int v)
{
u = get(u); v = get(v);
if (u==v) return false;
par[v] = u; return true;
}
} dsu;
int n,m,k,h;
vector<pair<int,ll>> adj[100005];
int a[100005];
double dist[100005][205];
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
n = N; m = M; k = K; h = H+1;
dsu.init(n);
FOR(i, 1, n) adj[i].clear();
FOR(i, 0, m-1)
{
int u = x[i]+1, v = y[i]+1;
if (u!=h && v!=h) dsu.merge(u,v);
adj[u].pb(mp(v, c[i]));
adj[v].pb(mp(u, c[i]));
}
FOR(i, 0, n-1) a[i+1] = arr[i];
k = min(k, 200);
FOR(i, 1, n) FOR(j, 0, k) dist[i][j] = LL_LIM;
priority_queue<pair<double,pii>, vector<pair<double,pii>>, greater<pair<double,pii>> > q;
dist[1][0] = 0; q.push(mp(0,mp(1,0)));
FOR(i, 2, n) if (a[i]==0 && dsu.get(i)==dsu.get(1))
{
dist[i][0] = 0; q.push(mp(0, mp(i,0)));
}
double ans = LL_LIM;
while (!q.empty())
{
int u = q.top().se.fi, cnt = q.top().se.se; double d = q.top().fi;
q.pop();
if (dist[u][cnt]<d) continue;
if (u==h)
{
minimize(ans, d);
continue;
}
for (auto V:adj[u])
{
int v = V.fi; double w = V.se;
if (minimize(dist[v][cnt], d+w))
{
q.push(mp(d+w, mp(v,cnt)));
}
if (a[v]==2 && cnt<k)
{
if (minimize(dist[v][cnt+1], (d+w)/2))
{
q.push(mp((d+w)/2, mp(v,cnt+1)));
}
}
}
}
return ans;
}
