#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
double solveNoTwos(int N, int M, int K, int H, vector<vector<pll>> G,
vector<int> arr) {
vector<bool> v(N);
priority_queue<pair<double, ll>, vector<pair<double, ll>>,
greater<pair<double, ll>>>
q;
arr[0] = 0;
{
vector<bool> v(N);
queue<ll> qt;
qt.push(0);
while (qt.size()) {
ll node = qt.front();
qt.pop();
if (v[node] || node == H) continue;
v[node] = true;
if (!arr[node]) q.push({0, node});
for (pll& nei : G[node]) qt.push(nei.first);
}
}
double ans = LLONG_MAX;
while (q.size()) {
ll node = q.top().second;
double c = q.top().first;
q.pop();
if (node == H) ans = min(ans, c);
if (v[node] || node == H) continue;
v[node] = true;
for (pll& nei : G[node]) q.push({nei.second + c, nei.first});
}
if (ans == LLONG_MAX) return -1;
return ans;
}
double solve3(int N, int M, int K, int H, vector<vector<pll>> G,
vector<int> arr) {
double ans = LLONG_MAX;
queue<pair<pair<ll, ll>, double>> q;
vector<bool> v(N);
q.push({{0, -1}, 0});
while (q.size()) {
ll node = q.front().first.first;
ll p = q.front().first.second;
double c = q.front().second;
q.pop();
if (arr[node] == 2) c /= 2;
if (arr[node] == 0) c = 0;
if (node == H) ans = min(ans, c);
if (v[node] || node == H) continue;
v[node] = true;
for (pll& nei : G[node])
if (nei.first != p && !v[nei.first])
q.push({{nei.first, node}, nei.second + c});
}
if (ans == LLONG_MAX) return -1;
return ans;
}
double solveChain(int N, int M, int K, int H, vector<int>& c,
vector<int> arr) {
if (M + 1 < H) return -1;
set<int> divs;
for (int i = H; i > 0 && divs.size() < K; i--)
if (arr[i] == 2) divs.insert(i);
double ans = 0;
for (int i = 1; i <= H; i++) {
ans += c[i - 1];
if (arr[i] == 0) ans = 0;
else if (arr[i] == 2 && divs.count(i))
ans /= 2;
}
return ans;
}
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<pll>> G(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]});
}
if (arr[H] == 0) return 0;
if (N == 2 || (G[0].size() == 1 && G[0][0].first == H)) {
if (!M) return -1;
if (arr[H] == 2) return G[0][0].second / double(2);
return G[0][0].second;
}
if (N == 3) return solve3(N, M, K, H, G, arr);
bool NoTwos = 1;
for (int& i : arr)
if (i == 2) {
NoTwos = 0;
break;
}
if (NoTwos) return solveNoTwos(N, M, K, H, G, arr);
return solveChain(N, M, K, H, c, arr);
}
