#pragma GCC optimize("O3,unroll-loops")
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> edges[100000];
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) {
for (int i=0;i<N;i++) edges[i].clear();
for (int i=0;i<M;i++) {
edges[x[i]].push_back({y[i],c[i]});
edges[y[i]].push_back({x[i],c[i]});
}
double dp[N][K+1];
for (int i=0;i<N;i++) {
for (int j=0;j<=K;j++) dp[i][j] = 2e18;
}
using wtf = pair<double,pair<int,int>>;
priority_queue<wtf,vector<wtf>,greater<wtf>> pq;
pq.push({0,{0,0}});
while (!pq.empty()) {
wtf f = pq.top();
pq.pop();
double cost = f.first;
int used = f.second.second;
int city = f.second.first;
if (dp[city][used] <= cost) continue;
dp[city][used] = cost;
for (auto it : edges[city]) {
int dest = it.first;
int go = it.second;
if (!arr[dest]) {
pq.push(make_pair(0,make_pair(dest,used)));
}
else if (arr[dest]) {
pq.push({cost+go,{dest,used}});
}
else {
if (used^K) pq.push({(cost+go)/2,{dest,used+1}});
pq.push({cost+go,{dest,used}});
}
}
}
return dp[H][K]==2e18?-1:dp[H][K];
}
