#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 100010
#define INF 1e303
#include <vector>
vector<pair<int,int>> adj[MAX_N];
bool reachable[MAX_N];
double dist[MAX_N];
void dfs(int node, int specialNode){
reachable[node] = true;
if (node!=specialNode){
for(auto a : adj[node]){
if (!reachable[a.first]){
dfs(a.first,specialNode);
}
}
}
}
struct P {
int dest;
double dist;
bool moved = true;
bool operator< (P other) const {
return dist > other.dist;
}
};
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
//clear all adjacency lists and reachables and best dist
for(int i=0;i<N;i++) adj[i].clear(), reachable[i]=false, dist[i]=INF;
//remake all adjacencies
for(int i=0;i<M;i++){
adj[x[i]].push_back({y[i],c[i]});
adj[y[i]].push_back({x[i],c[i]});
}
//run dfs to find all reachable nodes
dfs(0,H);
//if unreachable return
if (!reachable[H]) return -1;
reachable[H] = false;
//run base dijkstra, sourced at reachable 0s and start
priority_queue<P> todo;
todo.push({0,0});
for(int i=0;i<N;i++){
if (reachable[i] && arr[i]==0){
todo.push({i,0});
}
}
while(!todo.empty()){
P u = todo.top();
todo.pop();
if (u.dist < dist[u.dest]){
dist[u.dest] = u.dist;
if (u.dest != H){
for(auto a : adj[u.dest]){
if (u.dist + a.second < dist[a.first]){
todo.push({a.first,u.dist+a.second});
}
}
}
}
}
//printf("%lf %lf %lf\n",dist[0],dist[1],dist[2]);
//run at most K further dijkstras, sourced at reachable 0s and reachable doubles (using half of best dist)
for(int k=1;k<=K;k++){
bool changed = false;
//todo is already empty, so just add to it
for(int i=0;i<N;i++){
if (reachable[i]){
if (arr[i]==0){
todo.push({i,0});
//printf("%d %lf\n",i,0);
} else if (arr[i]==2){
todo.push({i,dist[i]/2,false});
//printf("%d %lf\n",i,dist[i]/2);
}
}
}
while(!todo.empty()){
P u = todo.top();
todo.pop();
if (u.dist < dist[u.dest]){
if (u.moved){
changed = true;
dist[u.dest] = u.dist;
}
if (u.dest != H){
for(auto a : adj[u.dest]){
if (u.dist + a.second < dist[a.first]){
todo.push({a.first,u.dist+a.second});
}
}
}
}
}
if (!changed) break;
}
return dist[H];
}
