#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
const double INF = numeric_limits<double>::max();
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) {
vector<vector<pair<int, double>>> 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]);
}
vector<vector<double>> dis(N, vector<double>(K + 1, INF));
dis[0][0] = 0;
set<tuple<double, int, int>> q;
q.emplace(dis[0][0], 0, 0);
while (!q.empty()) {
auto [w, nearest, i] = *q.begin();
q.erase(q.begin());
if(nearest == H) continue;
for (auto [to, weight]: g[nearest]) {
if (arr[to] == 0) weight = -dis[nearest][i];
if (dis[to][i] > dis[nearest][i] + weight) {
q.erase(tuple{dis[to][i], to, i});
dis[to][i] = dis[nearest][i] + weight;
q.emplace(dis[to][i], to, i);
}
if (arr[to] == 2 && i < K && dis[to][i + 1] > (dis[nearest][i] + weight) / 2.) {
q.erase(tuple{dis[to][i + 1], to, i + 1});
dis[to][i + 1] = (dis[nearest][i] + weight) / 2.;
q.emplace(dis[to][i + 1], to, i + 1);
}
}
}
double res = INF;
for (int i = 0; i <= K; ++i) res = min(dis[H][i], res);
if (res == INF) res = -1;
return res;
}
