#include "cyberland.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Edge {
int to;
int dst;
};
struct Node {
int at;
int op2;
double dst;
bool operator<(const Node& other) const {
if (dst != other.dst)
return dst > other.dst;
if (at != other.at)
return at < other.at;
return op2 < other.op2;
}
};
void initDfs(int node, vector<vector<Edge>>& adj, vector<bool>& vis, int H) {
vis[node] = true;
for (auto& x: adj[node])
if (x.to != H && !vis[x.to])
initDfs(x.to, adj, vis, H);
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
K = min(K, 77);
vector<vector<Edge>> 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]});
}
vector<vector<double>> dist (N);
for (int i = 0; i < N; i++)
dist[i].assign(K + 1, 1e18);
vector<bool> vis (N, false);
initDfs(0, adj, vis, H);
priority_queue<Node> nxt {};
arr[0] = 0;
for (int i = 0; i < N; i++) {
if (vis[i] && arr[i] == 0) {
dist[i][0] = 0;
nxt.push({i, 0, 0});
}
}
while (!nxt.empty()) {
auto cur = nxt.top();
nxt.pop();
if (cur.at == H)
continue;
if (dist[cur.at][cur.op2] == cur.dst) {
for (auto& x: adj[cur.at]) {
// no divide
double nxtDst = cur.dst + (double)x.dst;
if (nxtDst < dist[x.to][cur.op2]) {
dist[x.to][cur.op2] = nxtDst;
nxt.push({x.to, cur.op2, nxtDst});
}
// use divide
nxtDst /= 2;
if (arr[x.to] == 2 && cur.op2 < K && nxtDst < dist[x.to][cur.op2 + 1]) {
dist[x.to][cur.op2 + 1] = nxtDst;
nxt.push({x.to, cur.op2 + 1, nxtDst});
}
}
}
}
double ans = 1e18;
for (int i = 0; i <= K; i++)
ans = min(ans, dist[H][i]);
if (ans == 1e18)
ans = -1;
return ans;
}
