#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
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> a) {
k = min(k, 80);
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]);
}
const double inf = 1e18;
k += 1;
vector<double> dist(n * k, inf);
dist[0] = 0;
set<pair<double, int>> st;
st.emplace(0, 0);
double ans = inf;
vector<bool> was(n * k);
while (!st.empty()) {
auto it = st.begin();
int v = it->second;
st.erase(it);
int i = v / k;
int j = v % k;
if (i == h) {
ans = min(ans, dist[v]);
continue;
}
if (was[v]) {
continue;
}
was[v] = true;
for (auto& p : g[i]) {
int to = p.first;
int w = p.second;
if (a[to] == 0) {
if (dist[to * k + j] > 0) {
int nto = to * k + j;
/* if (st.find({dist[nto], nto}) != st.end()) {
st.erase(st.find({dist[nto], nto}));
} */
dist[nto] = 0;
st.emplace(dist[nto], nto);
}
}
if (dist[to * k + j] > dist[v] + w) {
int nto = to * k + j;
/* if (st.find({dist[nto], nto}) != st.end()) {
st.erase(st.find({dist[nto], nto}));
} */
dist[nto] = dist[v] + w;
st.emplace(dist[nto], nto);
}
if (a[to] == 2) {
if (j + 1 < k && dist[to * k + j + 1] > (dist[v] + w) / 2.000000) {
int nto = to * k + j + 1;
/* if (st.find({dist[nto], nto}) != st.end()) {
st.erase(st.find({dist[nto], nto}));
} */
dist[nto] = (dist[v] + w) / 2.000000;
st.emplace(dist[nto], nto);
}
}
}
}
if (ans == inf) {
ans = -1;
}
return ans;
}
/*
1
3 2 30
2
1 2 1
1 2 12
2 0 4
4.00000000000
1
4 4 30
3
1 0 2 1
0 1 5
0 2 4
1 3 2
2 3 4
2.00000000000
*/
