#include "cyberland.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define db long double
using namespace std;
int const n_max=1e5+10;
db len[n_max][100];
vector<pair<int,db>> node[n_max];
bitset<n_max> canend;
db ans=DBL_MAX;
void reset(int N,int K)
{
for(int i=0;i<=N;i++)for(int j=0;j<=K;j++)len[i][j]=DBL_MAX;
for(int i=0;i<=N;i++)node[i].clear();
canend.reset();
ans=DBL_MAX;
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
K=min(K,99);
if(H==0||arr[H]==0)return 0;
reset(N,K);
for(int i=0;i<M;i++)
{
node[x[i]].push_back({y[i],(db)c[i]});
node[y[i]].push_back({x[i],(db)c[i]});
}
canend[0]=true;
queue<int> qq;
qq.push(0);
while(!qq.empty())
{
int u=qq.front();
qq.pop();
for(auto it:node[u])
{
int v=it.fi;
if(canend[v]||v==H)continue;
canend[v]=true;
qq.push(v);
}
}
priority_queue<pair<pair<db,db>,pair<int,int>>,vector<pair<pair<db,db>,pair<int,int>>>,
greater<pair<pair<db,db>,pair<int,int>>>> q;
if(arr[H]!=2&&K>=1)q.push({{0,1},{K,H}});
else q.push({{0,0.5},{K-1,H}});
//for(int i=0;i<=K;i++)len[H][i]=0;
while(!q.empty())
{
db l=q.top().fi.fi,cost=q.top().fi.se;
int k=q.top().se.fi,u=q.top().se.se;
q.pop();
//cout<<l<<" "<<cost<<" "<<k<<" "<<u<<endl;
if(l>ans)continue;
if(len[u][k]<l)continue;
if(u==H&&l!=0)continue;
for(auto it:node[u])
{
int v=it.fi;
db nl=it.se*cost+l;
if(nl>ans)continue;
if(!canend[v])continue;
if(v==0)ans=nl;
if(arr[v]==0)
{
ans=nl;
if(len[v][k]>nl)
{
len[v][k]=nl;
continue;
}
}
else if(arr[v]==2&&k>=1)
{
if(len[v][k-1]>nl)
{
len[v][k-1]=nl;
q.push({{nl,cost/2},{k-1,v}});
//cout<<v<<endl;
}
continue;
}
else
{
if(len[v][k]>nl)
{
len[v][k]=nl;
q.push({{nl,cost},{k,v}});
//cout<<v<<endl;
}
}
}
}
if(ans==DBL_MAX)return -1;
else return ans;
}
