#include "cyberland.h"
#include <tuple>
#include <vector>
#include <queue>
#include <utility>
#define MAX_N 100001
#define MAX_M 200001
#define MAX_K 71
int head[MAX_N], nxt[MAX_M], vv[MAX_M], ww[MAX_M];
int ds[MAX_N];
int ds_find(int i){return ds[i]<0?i:(ds[i]=ds_find(ds[i]));}
double d[MAX_N][MAX_K];
void link(int u, int v, int w)
{
static int i =1;
nxt[i] = head[u];
vv[i] = v;
ww[i] = w;
head[u] = i++;
}
double solve(int n, int m, int kk, int h, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
if (kk >= MAX_K) kk = MAX_K - 1;
for (int i = 0; i < n; ++i) ds[i] = -1;
for (int i = 0; i < m; ++i) if (ds_find(x[i])!=ds_find(y[i]))ds[ds_find(y[i])]=ds_find(x[i]);
if (ds_find(0) != ds_find(h)) return -1;
for (int i = 0; i < n; ++i)
for (int j = 0; j <= kk; ++j)
d[i][j] = 1e18;
for (int i = 0; i < m; ++i)
link(x[i], y[i], c[i]), link(y[i], x[i], c[i]);
double z = 1e18;
arr[0]=0;
std::priority_queue<std::tuple<double, int, int> >pq;
for (int i = 0; i < n; ++i)
pq.emplace(d[h][0]=0, h, 0);
while (pq.size())
{
auto[c,u,k]=pq.top();pq.pop();c*=-1;
if (d[u][k] != c) continue;
if(arr[u]==0&&z>c)z=c;
for(int j=head[u];j;j=nxt[j])
{
if (d[vv[j]][k]>c+ww[j])
{
d[vv[j]][k]=c+ww[j];
pq.emplace(-d[vv[j]][k],vv[j],k);
}
if(arr[vv[j]]==2&&k+1<=kk)
{
if (d[vv[j]][k+1]>c/2+ww[j])
{
d[vv[j]][k+1]=c/2+ww[j];
pq.emplace(-d[vv[j]][k+1],vv[j],k+1);
}
}
}
}
return z;
}
