#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using key = pair<double, int>;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<vector<pair<int, int>>> g(N);
for (int i = 0; i < M; ++i) {
g[x[i]].emplace_back(y[i], c[i]);
g[y[i]].emplace_back(x[i], c[i]);
}
K = min(K, 100);
priority_queue<key, vector<key>, greater<key>> pq;
vector<vector<double>> dp(N, vector<double> (K + 2, -1));
dp[0][0] = 0;
for (int i = 1; i < N; ++i) {
if (arr[i] == 0) {
dp[i][0] = 0;
}
}
for (int k = 0; k <= K; ++k) {
for (int i = 0; i < N; ++i) {
if (dp[i][k] != -1) {
pq.emplace(dp[i][k], i);
}
}
while (!pq.empty()) {
auto [cost, v] = pq.top();
pq.pop();
if (cost != dp[v][k]) {
continue;
}
for (auto [u, w] : g[v]) {
double nc = cost + w;
if (dp[u][k] == -1 || nc < dp[u][k]) {
dp[u][k] = nc;
pq.emplace(dp[u][k], u);
}
if (arr[u] == 2) {
nc = nc / 2.0;
if (dp[u][k + 1] == -1 || nc < dp[u][k + 1]) {
dp[u][k + 1] = nc;
pq.emplace(dp[u][k + 1], u);
}
}
}
}
}
double ans = -1;
for (int i = 0; i <= K; ++i) {
if (dp[H][i] != -1 && (ans == -1 || ans > dp[H][i])) {
ans = dp[H][i];
}
}
return ans;
}
