#include <bits/stdc++.h>
#define ll int
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
const int MAXN = 1e5 + 1;
vector<pair<ll, ll>> grafo[MAXN];
ll ar[MAXN], h;
bool vis[MAXN];
vector<ll> pos;
struct nod
{
ll nodo, k;
double dis;
bool operator<(const nod &x)
const
{
return dis > x.dis;
}
};
bool ap = 0;
void dfs(ll nod)
{
if (nod == h)
{
ap = 1;
return;
}
vis[nod] = 1;
if (ar[nod] == 0 || nod == 0)
pos.pb(nod);
for (auto k : grafo[nod])
if (vis[k.fr] == 0)
dfs(k.fr);
}
void init(ll N)
{
pos.resize(0);
for (ll i = 0; i < N; i++)
{
grafo[i].resize(0);
vis[i] = 0;
}
ap = 0;
}
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, 80);
init(N);
ll i;
h = H;
for (i = 0; i < N; i++)
ar[i] = arr[i];
for (i = 0; i < M; i++)
{
grafo[x[i]].pb({y[i], c[i]});
grafo[y[i]].pb({x[i], c[i]});
}
priority_queue<nod> pq;
nod v;
vector<vector<double>> dist(N, vector<double>(K + 1, 1e14));
dfs(0);
if (ap == 0)
return -1;
for (auto k : pos)
{
v.k = 0;
v.nodo = k;
v.dis = 0;
dist[k][0] = 0;
pq.push(v);
}
for(i=0; i<=K; i++)
{
while (pq.size())
{
v = pq.top();
pq.pop();
if (v.nodo == H)
continue;
if (v.dis != dist[v.nodo][v.k])
continue;
for (auto k : grafo[v.nodo])
{
if (ar[k.fr] == 0)
continue;
nod nV;
nV.nodo = k.fr;
nV.k = v.k + 1;
nV.dis = (v.dis + k.se)/2;
if (ar[nV.nodo] == 2 && nV.k <= K && nV.dis < dist[k.fr][nV.k]&&nV.k==i+1)
{
dist[k.fr][nV.k] = nV.dis;
pq.push(nV);
}
nV.k--;
nV.dis = v.dis + k.se;
if (nV.dis < dist[k.fr][nV.k])
{
dist[k.fr][nV.k] = nV.dis;
pq.push(nV);
}
}
}
}
double mi = dist[H][0];
for (i = 1; i <= K; i++)
mi = min(mi, dist[H][i]);
return mi;
}
