#include "cyberland.h"
#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
const double inf = 1e100;
const int N = 100'010;
vector<pii> A[N];
int n;
vector<double> dij(vector<double> dis, int dst)
{
priority_queue<pair<double,int>, vector<pair<double,int>>, greater<pair<double,int>>> Q;
Loop (i,0,n)
Q.push({dis[i], i});
while (Q.size()) {
auto [d, v] = Q.top();
Q.pop();
if (d != dis[v])
continue;
if (v == dst)
continue;
for (auto [u, w] : A[v]) {
if (d + w >= dis[u])
continue;
dis[u] = d + w;
Q.push({dis[u], u});
}
}
return dis;
}
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) {
n = N;
Loop (i,0,n)
A[i].clear();
Loop (i,0,M) {
int v = x[i], u = y[i], w = c[i];
A[v].push_back({u, w});
A[u].push_back({v, w});
}
vector<double> dis(n, inf);
dis[0] = 0;
dis = dij(dis, H);
if (dis[H] == inf)
return -1;
Loop (i,0,n)
dis[i] = dis[i] != inf && arr[i] == 0? 0: inf;
dis[0] = 0;
double ans = inf;
Loop (_,0,min(K+1,90)) {
dis = dij(dis, H);
ans = min(ans, dis[H]);
vector<double> dis2(n, inf);
Loop (v,0,n) {
if (arr[v] != 2)
continue;
for (auto [u, w] : A[v])
dis2[u] = min(dis2[u], dis[v]/2 + w);
}
dis = dis2;
}
return ans;
}
