#include "cyberland.h"
#include "bits/stdc++.h"
#define ff first
#define ss second
using namespace std;
const double inf = 1e15;
double solve(int n,int m,int k,int h,vector<int> x,vector<int> y,vector<int> c,vector<int> arr){
vector <pair<int,int>> g[m+1];
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]});
}
queue <int> q;
vector <bool> vs(n);
vs[0] = 0;
q.push(0);
while (!q.empty()){
int nd = q.front();
q.pop();
if (nd == h)
continue;
for (auto [to,w] : g[nd]){
if (!vs[to]){
vs[to] = 1;
q.push(to);
}
}
}
if (!vs[h])
return -1.0;
k = min(k,70);
vector <vector <double>> d(n,vector <double> (k+1,inf));
priority_queue <pair<double,pair<int,int>>> pq;//cost,node,k1
d[0][0] = 0;
pq.push({0,{0,0}});
for (int i = 1;i < n;i++){
if (vs[i] && !arr[i]){
pq.push({0,{i,0}});
d[i][0] = 0;
}
}
while (!pq.empty()){
double w = pq.top().ff;
int nd = pq.top().ss.ff;
int k1 = pq.top().ss.ss;
pq.pop();
if (nd == h)
continue;
if (d[nd][k1] < -w)
continue;
for (auto v : g[nd]){
int to = v.ff;
double w1 = v.ss;
//normal
if (d[nd][k1] + w1 < d[to][k1]){
d[to][k1] = d[nd][k1]+w1;
pq.push({-d[to][k1],{to,k1}});
}
//special
if (k1 < k && arr[to] == 2){
double h = (d[nd][k1]+w1)/2.0;
if (d[to][k1] > h){
d[to][k1] = h;
pq.push({-d[to][k1],{to,k1+1}});
}
}
}
}
double p = inf;
for (int i = 0;i <= k;i++){
p = min(p,d[h][i]);
}
return p;
}
