#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
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) {
const double inf = 1e18;
K = min(K, 70);
double dis[N + 1][K + 1] = {{inf}};
vector<vector<pair<int, double>>> adj(N + 1);
vector<int> vis(N);
queue<int> q;
priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> pq;
for(int i = 0; i < M; ++i){
adj[x[i]].emplace_back(y[i], (double)(c[i]));
adj[y[i]].emplace_back(x[i], (double)(c[i]));
}
q.push(0);
vis[0] = 1;
while(!q.empty()){
int u = q.front(); q.pop();
if(u == H) continue;
for(auto [v, w]:adj[u]) if(!vis[v]) vis[v] = 1, q.push(v);
}
memset(dis[0], 0, sizeof(dis[0]));
pq.emplace(0.0, 0, 0);
for(int i = 0; i < N; ++i) if(vis[i] && arr[i] == 0) memset(dis[i], 0, sizeof(dis[i])), pq.emplace(0.0, i, 0);
while(!pq.empty()){
auto [w, u, k] = pq.top();
pq.pop();
if(dis[u][k] < w || u == H) continue;
if(k > 0 && dis[u][k] >= dis[u][k - 1]) continue;
for(auto [v, ww]:adj[u]){
if(dis[v][k] > dis[u][k] + ww){
dis[v][k] = dis[u][k] + ww;
pq.emplace(dis[v][k], v, k);
}
if(arr[v] == 2 && k < K){
if(dis[v][k + 1] > (dis[u][k] + ww) / 2.0){
dis[v][k + 1] = (dis[u][k] + ww) / 2;
pq.emplace(dis[v][k + 1], v, k + 1);
}
}
}
}
double ans = *min_element(dis[H], dis[H] + 1 + K);
if(ans == inf) return -1;
else return ans;
}
