#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
double solve1(int N, int M, int K, int H, vector<vector<pll>> g,
std::vector<int> arr) {
struct state {
ll usedK = 0;
ll passed = 0;
ll node = 0;
double time = 0;
};
double ans = INT_MAX;
queue<state> q;
q.push({0, 0, 0, 0});
while (q.size()) {
state now = q.front();
q.pop();
if (now.passed > 33 || now.usedK > K) continue;
if (now.node == H) {
if (arr[now.node] == 2 && now.usedK < K) now.time /= 2;
ans = min(now.time, ans);
continue;
}
for (pll& nei : g[now.node]) {
state newState = {now.usedK, now.passed + 1, nei.first,
now.time + nei.second};
if (arr[nei.first] == 0) newState.time = 0;
q.push(newState);
if (arr[nei.first] == 2 && newState.usedK < K
&& newState.time > 0) {
newState.usedK++;
newState.time /= 2;
q.push(newState);
}
}
}
if (ans == INT_MAX) return -1;
return ans;
}
double solve2(int N, int M, int K, int H, vector<vector<pll>> g,
std::vector<int> arr) {
priority_queue<pair<double, ll>, vector<pair<double, ll>>,
greater<pair<double, ll>>>
q;
double ans = INT_MAX;
q.push({0, 0});
vector<bool> vis(N);
while (q.size()) {
ll node = q.top().second;
double cost = q.top().first;
q.pop();
if (node == H) {
ans = min(cost, ans);
continue;
}
if (vis[node]) continue;
vis[node] = true;
for (pll& nei : g[node])
if (!vis[nei.first])
q.push({nei.second + cost, nei.first});
}
if (ans == INT_MAX) return -1;
return ans;
}
double solve3(int N, int M, int K, int H, vector<vector<pll>> g,
std::vector<int> arr) {
priority_queue<pair<double, ll>, vector<pair<double, ll>>,
greater<pair<double, ll>>>
q;
double ans = INT_MAX;
q.push({0, H});
vector<bool> vis(N), reach(N);
{
queue<ll> qt;
qt.push(0);
while (qt.size()) {
ll node = qt.front();
qt.pop();
if (reach[node]) continue;
reach[node] = true;
for (pll& nei : g[node])
if (!reach[nei.first]) qt.push(nei.first);
}
}
while (q.size()) {
ll node = q.top().second;
double cost = q.top().first;
q.pop();
if (arr[node] == 0 && reach[node]) {
ans = cost;
break;
}
if (vis[node]) continue;
vis[node] = true;
for (pll& nei : g[node])
if (!vis[nei.first])
q.push({nei.second + cost, nei.first});
}
if (ans == INT_MAX) return -1;
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) {
if (arr[H] == 0) return 0;
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]});
}
bool allOnes = 1;
for (int& i : arr)
if (i != 1) {
allOnes = 0;
break;
}
if (N <= 3) return solve1(N, M, K, H, G, arr);
if (allOnes) return solve2(N, M, K, H, G, arr);
return solve3(N, M, K, H, G, arr);
}
