#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> pouvoirs;
vector<int> dejaVu;
set<int> zeroAccess;
int fin;
struct Arc{
int dest;
int poids;
};
vector<vector<Arc>> adj;
struct Sit{
int node;
int nbDiv;
double pow2;
double dis;
bool operator <(const Sit &other) const{
return dis > other.dis;
}
};
void dfs(int n){
if(dejaVu[n]) return;
dejaVu[n] = 1;
if(n == fin) return;
if(pouvoirs[n] == 0) zeroAccess.insert(n);
for(Arc arc : adj[n]){
if(!dejaVu[arc.dest])
dfs(arc.dest);
}
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
pouvoirs = arr;
fin = H;
K = min(K, 70);
dejaVu = vector<int>(N, 0);
adj = vector<vector<Arc>>(N);
for(int n=0; n<M; n++){
adj[x[n]].push_back({y[n], c[n]});
adj[y[n]].push_back({x[n], c[n]});
}
zeroAccess.clear();
zeroAccess.insert(0);
dfs(0);
if(!dejaVu[fin]) return -1;
vector<vector<int>> deja(N, vector<int>(K+1));
vector<vector<double>> distances(N, vector<double>(K+1, 1e17));
distances[fin][0]=0;
priority_queue<Sit> aTraiter;
aTraiter.push({fin, 0, 1, 0});
while(!aTraiter.empty()){
Sit curSit = aTraiter.top();
aTraiter.pop();
if(curSit.node == fin && curSit.nbDiv != 0) continue;
if(deja[curSit.node][curSit.nbDiv]) continue;
if(zeroAccess.count(curSit.node)) return curSit.dis;
deja[curSit.node][curSit.nbDiv] = 1;
for(Arc voisin : adj[curSit.node]){
int v = voisin.dest;
int w = voisin.poids;
if( distances[curSit.node][curSit.nbDiv] + w/curSit.pow2 < distances[v][curSit.nbDiv]){
distances[v][curSit.nbDiv] = distances[curSit.node][curSit.nbDiv] + w/curSit.pow2;
aTraiter.push({v, curSit.nbDiv, curSit.pow2, distances[v][curSit.nbDiv]});
}
if(pouvoirs[v] == 2 && curSit.nbDiv < K){
if(distances[curSit.node][curSit.nbDiv] + w/curSit.pow2 < distances[v][curSit.nbDiv + 1]){
distances[v][curSit.nbDiv + 1] = distances[curSit.node][curSit.nbDiv] + w/curSit.pow2;
aTraiter.push({v, curSit.nbDiv+1, curSit.pow2*2, distances[v][curSit.nbDiv + 1]});
}
}
}
}
return -1;
}
