#include <bits/stdc++.h> using namespace std; using pii=pair<int,int>; constexpr int N=1e5+5,KX=67; constexpr double INF=1e99; int n,m,kk,h,ty[N]; vector<pii> g[N]; bool reach[N]; double f[N][KX+3][2]; vector<int> st; inline void bfsinit(int s){ queue<int> q; memset(reach,0,n*sizeof(bool)); reach[s]=true, q.emplace(s); while(!q.empty()){ int u{q.front()};q.pop(); for(auto e:g[u]){ int v{e.first}; if(!reach[v]){ reach[v]=true, q.emplace(v); } } } } inline void dijx(){ struct Q{ int u,d; double dis; bool div2; Q(){} Q(int u,int d,double ds,bool d2): u{u},d{d},dis{ds},div2{d2}{} inline bool operator<(const Q &b)const{ return dis>b.dis; } }; queue<Q> q; static bool inq[N][KX+3][2]; for(int i{0};i<n;++i){ for(int j{0};j<=kk;++j){ f[i][j][0]=f[i][j][1]=INF; inq[i][j][0]=inq[i][j][1]=false; } } for(int s:st){ f[s][0][0]=0.0; q.emplace(s,0,f[s][0][0],false); inq[s][0][0]=true; } while(!q.empty()){ auto t=q.front();q.pop(); inq[t.u][t.d][t.div2]=false; double tdis=f[t.u][t.d][t.div2]; if(t.d<kk&&!t.div2&&ty[t.u]==2&&tdis/2.0<f[t.u][t.d+1][1]){ f[t.u][t.d+1][1]=tdis/2.0; if(!inq[t.u][t.d+1][1]){ q.emplace(t.u,t.d+1,f[t.u][t.d+1][1],true); inq[t.u][t.d+1][1]=true; } } for(pii e:g[t.u]){ int v{e.first},w{e.second}; if(tdis+w<f[v][t.d][0]){ f[v][t.d][0]=tdis+w; if(!inq[v][t.d][0]){ q.emplace(v,t.d,f[v][t.d][0],false); inq[v][t.d][0]=true; } } } } } 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){ n=N,m=M,kk=K,h=H; kk=min(kk,KX); for(int i{0};i<n;++i){ ty[i]=arr[i]; g[i].clear(); } for(int i{0};i<m;++i){ int u{x[i]},v{y[i]},w{c[i]}; if(u!=h) g[u].emplace_back(v,w); if(v!=h) g[v].emplace_back(u,w); } bfsinit(0); if(!reach[h]) return -1; for(int i{0};i<n;++i){ if(i==0||(ty[i]==0&&reach[i])){ st.emplace_back(i); } } dijx(); double ans{INF}; for(int i{0};i<=kk;++i){ ans=min({ans,f[h][i][0],f[h][i][1]}); } st.clear(); return ans; }