#include <bits/stdc++.h>
using namespace std;
#include "cyberland.h"
const int MxN = 1e5+10;
double dist[100][MxN];
vector<pair<int, double>> adj[MxN];
struct state_t{
double d;
int u, s;
bool operator<(const state_t& o) const{
return d > o.d;
}
};
bool vis[MxN];
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) {
K = min(K, 90);
memset(vis, 0, sizeof vis);
for(int i = 0; i <= K; ++i) for(int j = 0; j <= N; ++j) dist[i][j] = 1e18;
for(int i = 0; i < N; ++i) adj[i].clear();
for(int i = 0; i < M; ++i){
adj[x[i]].push_back({y[i], 1.0*c[i]});
adj[y[i]].push_back({x[i], 1.0*c[i]});
}
queue<int> q;
while(!q.empty()){
int u = q.front(); q.pop();
for(auto [v, w] : adj[u]){
if(!vis[v]) vis[v] = 1, q.push(v);
}
}
priority_queue<state_t> pq;
for(int i = 0; i < N; ++i) if(vis[i] && arr[i] == 0) memset(dist[i], 0, sizeof dist[i]), pq.push({0, i, 0});
while(!pq.empty()){
state_t cur = pq.top(); pq.pop();
if(dist[cur.s][cur.u] < cur.d) continue;
if(cur.u == H) continue;
for(auto [v, w] : adj[cur.u]){
if(arr[v] == 0){
if(dist[0][v] > 0) pq.push({dist[0][v] = 0, v, 0});
}else if(arr[v] == 2 && cur.s < K){
if(dist[cur.s+1][v] > (w+cur.d)/2) pq.push({dist[cur.s+1][v] = (w+cur.d)/2, v, cur.s+1});
}
if(dist[cur.s][v] > w+cur.d) pq.push({dist[cur.s][v] = w+cur.d, v, cur.s});
}
}
double ans = 1e18;
for(int i = 0; i <= K; ++i) ans = min(ans, dist[i][H]);
return (ans == 1e18 ? -1 : ans);
}
