#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MXN = 1e5 + 5;
int n, m, k, h;
vector<pair<int, double>> adj[MXN];
int arr[MXN];
double dist[MXN], ndist[MXN];
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
vector<int> nodes;
void dijk(int s, int F)
{
while (!pq.empty()) pq.pop();
for (int i = 0; i < n; i++) ndist[i] = -1;
for (int &x : nodes) ndist[x] = 0;
if (!F)
for (int i = 0; i < n; i++)
{
if (arr[i] != 2) continue;
for (pair<int, double> &v : adj[i])
{
if (v.first == h) continue;
if (dist[v.first] == -1) continue;
if (ndist[i] == -1) ndist[i] = (dist[v.first] + v.second) / 2;
else ndist[i] = min(ndist[i], (dist[v.first] + v.second) / 2);
}
}
for (int i = 0; i < n; i++)
{
if (ndist[i] != -1) pq.push({ndist[i], i});
}
while (!pq.empty())
{
pair<double, int> f = pq.top();
pq.pop();
if (ndist[f.second] > f.first) continue;
if (f.second == h) continue;
for (pair<int, double> &v : adj[f.second])
{
if (ndist[v.first] == -1) ndist[v.first] = f.first + v.second;
else if (ndist[v.first] > f.first + v.second)
{
ndist[v.first] = f.first + v.second;
pq.push({ndist[v.first], v.first});
}
}
}
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> ARR)
{
n = N, m = M, k = K, h = H;
k = min(k, 70);
for (int i = 0; i < n; i++) adj[i].clear(), arr[i] = ARR[i], dist[i] = -1;
nodes.clear();
for (int i = 0; i < m; i++)
{
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
vector<int> u(n, 0);
queue<int> q;
u[0] = 1, q.push(0);
while (!q.empty())
{
int f = q.front();
q.pop();
if (f == h) continue;
for (pair<int, double> &v : adj[f])
{
if (u[v.first]) continue;
u[v.first] = 1, q.push(v.first);
}
}
for (int i = 0; i < n; i++)
{
if (u[i] && (!i || arr[i] == 0))
{
dist[i] = 0;
nodes.push_back(i);
}
else dist[i] = -1;
}
double res = -1;
for (int i = 0; i <= K; i++)
{
dijk(0, !i);
for (int j = 0; j < n; j++) dist[i] = ndist[i];
if (dist[h] != -1)
{
if (res == -1) res = dist[h];
else res = min(res, dist[h]);
}
}
return res;
}
