#include "cyberland.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define pb push_back
using namespace std;
constexpr int MAX = 2e+5 + 1, MOD = 1e9 + 7;
constexpr double INF = 2e+17;
int N, K, H;
vector <int> v, can;
vector <pair<int, double>> g[MAX+2];
vector <vector <double>> dis;
double res = INF;
void dijkstra(int id) {
priority_queue <pair<double, int>, vector <pair<double, int>>, greater<pair<double, int>>> q;
if (id == 0) {
for (int i = 1; i <= N; i++) {
if (can[i] && v[i] == 0 || i == 1) {
dis[i][id] = 0;
q.push({0, i});
}
}
}
else {
for (int i = 1; i <= N; i++) {
if (!can[i] || i == H) continue;
if (v[i] == 0 || i == 1) {
dis[i][id] = 0;
q.push({0, i});
}
for (auto [j, c] : g[i]) {
if (dis[i][id-1] >= INF / 10.) continue;
if (v[j] == 2) {
dis[j][id] = min(dis[j][id], (dis[i][id-1] + c) / 2.);
}
}
}
for (int i = 1; i <= N; i++) {
if (can[i] && v[i] == 2 && dis[i][id] != INF) q.push({dis[i][id], i});
}
}
while (!q.empty()) {
auto [d, u] = q.top();
q.pop();
if (u == H) continue;
if (d > dis[u][id]) continue;
for (auto [to, c] : g[u]) {
double nd = d + c;
if (dis[to][id] > nd) {
dis[to][id] = nd;
q.push({nd, to});
}
}
}
}
void bfs() {
queue <int> q;
can[1]= 1;
q.push(1);
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == H) continue;
for (auto [i,c] : g[u]) {
if (can[i]) continue;
can[i] = 1;
q.push(i);
}
}
}
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) {
k = min(k, 70);
++h;
for (int i = 0; i < m; i++) x[i]++, y[i]++;
v.clear();
v.pb(0);
for (int &i : arr) v.pb(i);
dis.assign(n+1, vector <double>(k+1, INF));
N = n, K = k, H = h;
for (int i= 0; i < m; i++) {
g[x[i]].pb({y[i], c[i]});
g[y[i]].pb({x[i], c[i]});
}
can.assign(n+1, 0);
bfs();
for (int i = 0; i <= k; i++) dijkstra(i);
for (int i = 1; i <= n; i++) g[i].clear();
res = INF;
double ans = min(res, *min_element(all(dis[h])));
return (ans >= INF ? -1 : ans);
}
