#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define ll __int128
#define VAR pair < pair < ll , ll > , pair < int , int > >
const int MAXK = 31;
inline ll ABS(ll a){
if(a < 0)return -a;
return a;
}
inline ll GCD(ll a , ll b){
a = ABS(a) , b = ABS(b);
while(a and b){
if(a > b)swap(a,b);
else if(a == 0)return b;
else {
b %= a;
swap(a,b);
}
}
return b;
}
inline pair < ll , ll > subt(pair < ll , ll > a , pair < ll , ll > b){
// cout << "gh1" << endl;
ll pay = a.first * b.second - a.second * b.first;
ll payda = a.second * b.second;
ll gc = GCD(pay , payda);
if(pay < 0 and payda < 0)gc *= -1;
// cout << "gh2 : " << pay << " " << payda << " " << gc << endl;
// cout << pay/gc << endl;
// cout << payda/gc << endl;
// cout << "finished" << endl;
return {pay/gc , payda/gc};
}
struct cmp{
bool operator()(VAR a , VAR b){
return a.first.first * b.first.second < a.first.second * b.first.first;
}
};
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) {
// cout << "starting " << endl;
bitset < 31 > vis[n];
fill(vis , vis + n , 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]});
}
priority_queue < VAR , vector < VAR > , cmp > pq;//dist , node , how much k used
pq.push({{0,1},{0,0}});
function < void (int) > dfs = [&](int cur){
if(vis[cur] == 1 or cur == h)return;
vis[cur] = 1;
if(arr[cur] == 0){
pq.push({{0,1},{cur,0}});
// cout << "pushed : " << cur << endl;
}
for(auto itr : graph[cur]){
dfs(itr.first);
}
};
// cout << "flag0 " << endl;
dfs(0);
fill(vis , vis + n , 0);
double ans = 1;
// cout << "flag1 " << endl;
while(pq.size()){
VAR tmp = pq.top();
pq.pop();
if(vis[tmp.second.first][tmp.second.second])continue;
vis[tmp.second.first][tmp.second.second] = 1;
// cout << "pq : " << tmp.first.first << " / " << tmp.first.second << " , " << tmp.second.first << " " << tmp.second.second << endl;
double reelval = (double)tmp.first.first / (double)tmp.first.second;
if(tmp.second.first == h){
// cout << "flag1.1" << endl;
if(ans == 1 or ans < reelval){
ans = reelval;
}
// cout << "flag1.2" << endl;
}
else{
// cout << "flag2.1" << endl;
for(auto itr : graph[tmp.second.first]){
if(arr[tmp.second.first] == 2 and tmp.second.second < k){
pq.push({subt({tmp.first.first , tmp.first.second * 2ll},{itr.second , 1ll}) , {itr.first , tmp.second.second+1}});
}
pq.push({subt(tmp.first , {itr.second , 1ll}) , {itr.first , tmp.second.second}});
}
// cout << "flag2.2" << endl;
}
}
// cout << "flag3 " << endl;
return -ans;
}
