#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pi> vpi;
typedef vector<vpi> vvpi;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back
typedef double ld;
typedef vector<double> vd;
typedef pair<double, int> pdi;
typedef vector<ld> vld;
typedef pair<ld, int> pldi;
const int max_K = 70;
template<typename T>
void print_vec(const vector<T>& v) {
for(T vv : v) cerr << vv << " ";
cerr << endl;
}
double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) {
vvpi adj;
K = min(K, max_K); // ! clamping K to a certain maximum
for(int i = 0; i < N; i++) {
vpi adjr;
adj.pb(adjr);
}
for(int i = 0; i < M; i++) {
adj[x[i]].pb({y[i], c[i]});
adj[y[i]].pb({x[i], c[i]});
// Divide by 2 ability
// if(arr[x[i]] == 2) {
// adj[y[i]].pb({x[i], c[i]});
// }
}
// Run BFS to see which are part of the same connected component
vb visitable(N, false);
queue<int> q;
q.push(0);
while(!q.empty()) {
int i = q.front();
q.pop();
if(visitable[i]) continue;
visitable[i] = true;
if(i == H) continue;
for(auto [j, _] : adj[i]) q.push(j);
}
if(!visitable[H]) return -1;
// Find all superpower countries
vi set_0;
vi div_2;
for(int i = 0; i < N; i++) {
if(!visitable[i]) continue;
if(arr[i] == 0) set_0.pb(i);
if(arr[i] == 2) div_2.pb(i);
}
// Populate distance array
ld ans = INF(ld);
vld dist(N, INF(ld));
typedef priority_queue<pldi, vector<pldi>, greater<pldi>> PQ; // ! greater is used for min priority queue
PQ pq;
for(int v : set_0) {
pq.push({0.0, v});
dist[v] = 0.0;
}
pq.push({0.0, 0});
dist[0] = 0.0;
for(int k_rep = 0; k_rep <= K; k_rep++) {
// Run Dijkstra's on the new distances
vb vis(N, false);
while(!pq.empty()) {
auto [cd, i] = pq.top();
// cerr << cd << " " << i << endl;
pq.pop();
if(vis[i]) continue;
vis[i] = true;
dist[i] = cd;
if(i == H) continue;
for(auto [j, cost] : adj[i]) {
pq.push({cd + (ld)(cost), j});
}
}
// print_vec(dist);
ans = min(ans, dist[H]);
// Apply powerups
// vld newdist(N, INF(ld));
for(int i : set_0) {
// newdist[i] = 0.0;
pq.push({0.0, i});
}
for(int i : div_2) {
ld min_dist = INF(ld);
// if(dist[i] != INF(ld)) min_dist = dist[i] * 0.5L;
for(auto [j, cost] : adj[i]) {
/*
For each neighbor of a divide-by-2 node,
if it was reached, consider the cost
*/
if(dist[j] != INF(ld) && j != H) {
min_dist = min(min_dist, (dist[j] + (ld)(cost)) * 0.5);
}
}
// min_dist = min(min_dist, dist[i]);
// newdist[i] = min_dist;
if(min_dist != INF(ld)) {
pq.push({min_dist, i});
}
}
// Consider the other nodes
for(int i = 0; i < N; i++) {
if(!visitable[i]) continue;
pq.push({dist[i], i});
// newdist[i] = min(newdist[i], dist[i]);
}
for(int i = 0; i < N; i++) {
dist[i] = INF(ld);
}
// dist = newdist;
}
return (ans == INF(double) ? -1 : (double)(ans));
}
