#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair < double , pair < int , int > > VAR;
const int MAXK = 31;
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) {
bitset < 31 > vis[n];
for(int i = 0;i<n;i++){
vis[i] = 0;
}
priority_queue < VAR > pq;//dist , node , how much k used
pq.push({0,{0,0}});
for(int i = 0;i<n;i++){
if(arr[i] == 0){
pq.push({0,{i,0}});
}
}
vector < pair < int , int > > graph[n];
for(int i = 0;i<m;i++){
graph[x[i]].push_back({y[i] , c[i]});
graph[y[i]].push_back({x[i] , c[i]});
}
double ans = -1;
while(pq.size()){
VAR tmp = pq.top();
pq.pop();
if(vis[tmp.second.first][tmp.second.second])continue;
//cout << "pq : " << tmp.first << " " << tmp.second.first << " " << tmp.second.second << endl;
vis[tmp.second.first][tmp.second.second] = 1;
if(tmp.second.first == (n-1)){
if(ans == -1 or ans < tmp.first){
ans = tmp.first;
}
}
//use an ability in here
if(arr[tmp.second.first] == 2 and tmp.second.second < k){
pq.push({tmp.first / 2 , {tmp.second.first , tmp.second.second + 1}});
}
//go to another vertex
for(auto itr : graph[tmp.second.first]){
pq.push({tmp.first - itr.second , {itr.first , tmp.second.second}});
}
}
return -ans;
}
