#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
using ld = double; using vi = vector<int>;
const ld INF = 1e18;
double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) {
ld tmin[N][K+1];
bool dfsf[N];
for (ll i=0;i<N;i++) {
dfsf[i]=0;
for (ll k=0;k<=K;k++) {
tmin[i][k]=INF;
}
}
vector<pii> adj[N]; //vertex,cost
for (ll i=0;i<M;i++) {
adj[x[i]].push_back({y[i],c[i]});
adj[y[i]].push_back({x[i],c[i]});
}
stack<int> s;
s.push(0);
while (!s.empty()) {
ll x0 = s.top(); s.pop();
if (!dfsf[x0]) {
dfsf[x0]=1;
if (x0==H) {
continue;
}
for (pii p0: adj[x0]) {
s.push(p0.first);
}
}
}
if (!dfsf[H]) {
return -1.0;
}
priority_queue<pair<ld,ll>> pq[K+1]; //{#k,{time,position}}
pq[0].push({0.0,0});
for (ll i=0;i<N;i++) {
if (dfsf[i] && (arr[i]==0)) {
pq[0].push({0.0,i});
}
}
for (ll k=0;k<=K;k++) {
while (!pq[k].empty()) {
auto A = pq[k].top(); pq[k].pop();
ld T = A.first; ll x0 = A.second;
if (arr[x0]==0 && T != 0.0) {
continue;
}
if (tmin[x0][k]<=(T+1e-10)) {
continue;
}
tmin[x0][k]=T;
if (x0==H) {
continue;
}
for (pii p0: adj[x0]) {
ll y0 = p0.first; ld ce = p0.second;
pq[k].push({ce+T,y0});
if (arr[x0]==2 && k<K) {
pq[k+1].push({ce+T/2,y0});
}
}
}
}
ld ans = INF;
for (ll k=0;k<=K;k++) {
ans = min(ans,tmin[H][k]);
}
return ans;
}
