#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
double solve(int n, int m, int K, int h,
vector<int> x, vector<int> y, vector<int> c,
vector<int> arr)
{
// build undirected graph
vector<vector<pair<int,int>>> adj(n);
for(int i = 0; i < m; i++){
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
// dist[v][k] = minimum cost from h→v having used exactly k "doublings"
const double INF = 1e15;
vector<vector<double>> dist(n, vector<double>(31, INF));
dist[h][0] = 0.0;
// min-heap of (current_distance, node, used_k)
using T = tuple<double,int,int>;
priority_queue<T, vector<T>, greater<T>> pq;
pq.emplace(0.0, h, 0);
while(!pq.empty()){
auto [cd, v, k] = pq.top();
pq.pop();
// skip stale
if (cd > dist[v][k]) continue;
for(auto &e : adj[v]){
int to = e.first, w = e.second;
// 1) normal move, no doubling
double nd = cd + w;
if (nd < dist[to][k]){
dist[to][k] = nd;
pq.emplace(nd, to, k);
}
// 2) if city 'to' is type‑2, you may spend one doubling
if (arr[to] == 2 && k < 30){
double nd2 = 2.0 * nd;
if (nd2 < dist[to][k+1]){
dist[to][k+1] = nd2;
pq.emplace(nd2, to, k+1);
}
}
}
}
// quick reachability check (undirected)
vector<char> vis(n, 0);
function<void(int)> dfs = [&](int u){
vis[u] = 1;
for(auto &e: adj[u]){
if (!vis[e.first]) dfs(e.first);
}
};
dfs(0);
if (!vis[h]) return -1; // no path between 0 and h
// now compute best possible answer
double ans = INF;
// first consider reaching node 0 itself
double scale = 1.0;
for(int k = 0; k <= min(K, 30); k++){
ans = min(ans, dist[0][k] / scale);
scale *= 2.0;
}
// then consider every other special city i with arr[i]!=0
for(int i = 1; i < n; i++){
if (arr[i] != 0 && vis[i]){
double t = 1.0;
for(int k = 0; k <= min(K, 30); k++){
ans = min(ans, dist[i][k] / t);
t *= 2.0;
}
}
}
return ans;
}
