#include "cyberland.h"
#include <cmath>
#include <vector>
#include <cassert>
#include <algorithm>
#include <set>
#include <bitset>
using namespace std;
const int MAXN = 1e5 + 123;
const double INF = 1e18 + 177013;
vector<pair<int, int>> edg[MAXN];
bitset<MAXN> used;
void dfs_connect(int v, int H) {
if (used[v])
return;
used[v] = 1;
if (v == H)
return;
for (auto [u, d] : edg[v]) {
dfs_connect(u, H);
}
}
void initialize(int N, int M, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
for (int i = 0; i < N; ++i) {
edg[i].clear();
}
used = 0;
for (int i = 0; i < M; ++i) {
edg[x[i]].push_back({y[i], c[i]});
edg[y[i]].push_back({x[i], c[i]});
}
}
vector<double> bfs(int N, const vector<pair<double, int>>& inits, double mod) {
vector<double> depth(N, INF);
set<pair<double, int>> rdepth;
used = 0;
for (const auto &[d, v] : inits) {
depth[v] = d;
rdepth.insert({d, v});
}
while (rdepth.size()) {
const auto [d, v] = *rdepth.begin();
rdepth.erase(rdepth.begin());
for (auto [u, len] : edg[v]) {
if (d + len * mod < depth[u]) {
rdepth.erase({depth[u], u});
depth[u] = d + len * mod;
rdepth.insert({depth[u], u});
}
}
}
return depth;
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
initialize(N, M, x, y, c, arr);
dfs_connect(0, H);
if (!used[H])
return -1;
double __end_mod = 1;
if (arr[H] == 0)
return 0;
if (arr[H] == 2 && K > 0) {
arr[H] = 1;
--K;
__end_mod = 0.5;
}
bitset<MAXN> start;
for (int i = 0; i < N; ++i) {
start[i] = used[i] & (i == 0 || arr[i] == 0);
}
bitset<MAXN> div2;
for (int i = 0; i < N; ++i) {
div2[i] = arr[i] == 2 && used[i];
}
K = min({K, 120});
vector<double> depth;
double ans = INF;
depth = bfs(N, {{0, H}}, 1);
for (int i = start._Find_first(); i < N; i = start._Find_next(i))
ans = min(ans, depth[i]);
for (auto [u, d] : edg[H]) {
edg[u].erase(find(edg[u].begin(), edg[u].end(), pair<int, int>(H, d)));
}
for (int ki = 1; ki <= K; ++ki) {
vector<pair<double, int>> pts;
for (int i = div2._Find_first(); i < N; i = div2._Find_next(i)) {
pts.push_back({depth[i], i});
}
double mod = pow(0.5, ki);
depth = bfs(N, pts, mod);
for (int i = start._Find_first(); i < N; i = start._Find_next(i))
ans = min(ans, depth[i]);
vector<double> ndepth(N, INF);
for (int i = div2._Find_first(); i < N; i = div2._Find_next(i)) {
for (auto [u, d] : edg[i])
ndepth[i] = min(ndepth[i], depth[u] + d * mod);
}
for (int i = div2._Find_first(); i < N; i = div2._Find_next(i)) {
depth[i] = ndepth[i];
}
}
return ans * __end_mod;
}
