#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
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) {
const int mxk = 70;
k=min(k,mxk-2);
double tim[n][mxk];
for(int i = 0;i<n;i++){
for(int j = 0;j<mxk;j++){
tim[i][j]=2e18;
}
}
vector<array<int,2>>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]});
}
set<tuple<double,int,int>>pq;
pq.insert({0,0,0});
tim[0][0]=0;
//{time,index,usedk}
while(!pq.empty()){
tuple<double,int,int>curr = *(pq.begin());
pq.erase(pq.begin());
if(tim[get<1>(curr)][get<2>(curr)]!=get<0>(curr)){
continue;
}
if(get<1>(curr)==h)
continue;
for(array<int,2>e:g[get<1>(curr)]){
if(arr[get<1>(curr)]==0){
if(tim[e[0]][0]>e[1]){
pq.erase({tim[e[0]][0],e[0],0});
pq.insert({e[1],e[0],0});
tim[e[0]][0]=e[1];
}
}
else {
if(tim[e[0]][get<2>(curr)]>get<0>(curr)+e[1]){
pq.erase({tim[e[0]][get<2>(curr)],e[0],get<2>(curr)});
pq.insert({get<0>(curr)+e[1],e[0],get<2>(curr)});
tim[e[0]][get<2>(curr)]=get<0>(curr)+e[1];
}
if(arr[get<1>(curr)]==2&&get<2>(curr)<k){
if(tim[e[0]][get<2>(curr)+1]>(get<0>(curr)/2)+e[1]){
pq.erase({tim[e[0]][get<2>(curr)+1],e[0],get<2>(curr)+1});
pq.insert({(get<0>(curr)/2)+e[1],e[0],get<2>(curr)+1});
tim[e[0]][get<2>(curr)+1]=(get<0>(curr)/2)+e[1];
}
}
}
}
}
double ans = 2e18;
for(int i = 0;i<mxk;i++){
ans=min(ans,tim[h][i]);
}
if(ans==2e18){
return -1;
}
else{
return ans;
}
}
