#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
constexpr double inf = 1e18;
vector<int> t;
vector<vector<pair<int, double>>> g;
vector<double> get(int st, int n, int h) {
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
vector<double> d(n, inf);
d[st] = 0;
pq.push({0, st});
while (!pq.empty()) {
auto [k, u] = pq.top();
pq.pop();
if (k > d[u]) continue;
for (auto [v, w] : g[u]) {
if (t[v] == 0) {
d[v] = 0;
pq.push({0, v});
continue;
}
if (d[v] > k + w) {
d[v] = k + w;
if (v == h) continue;
pq.push({d[v], v});
}
}
}
return d;
}
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
t = arr;
g.assign(n, {});
for (int i = 0; i < m; i++) {
g[x[i]].push_back({y[i], c[i]});
g[y[i]].push_back({x[i], c[i]});
}
vector<double> dp = get(0, n, h);
if (dp[h] == -1) return -1;
k = min(k, 100);
while (k--) {
int pos = -1;
double mn = dp[h];
for (int i = 0; i < n; i++) {
if (arr[i] != 2) continue;
for (auto &[j, w] : g[i]) {
w /= 2;
}
get(0, n, h);
if (dp[h] < mn) {
pos = i;
}
for (auto &[j, w] : g[i]) {
w *= 2;
}
}
if (pos == -1) break;
for (auto &[u, w] : g[pos]) {
w /= 2;
}
dp = get(0, n, h);
}
return dp[h];
}
