#include "cyberland.h"
#include <vector>
#include <queue>
using namespace std;
using ld = long double;
const int NMAX = 1e5;
const ld INF = 1e18;
vector<pair<int , ld> > adj[NMAX+1];
ld dist[60][NMAX+1];
vector<int> arr;
int n, m, k, h;
bool reach[NMAX+1];
void bfs ()
{
queue<int> q;
q.push(0);
reach[0] = 1;
while (q.size())
{
int nod = q.front();
q.pop();
for (auto &edg : adj[nod])
{
int to = edg.first;
if (!reach[to] && to != h) {
reach[to] = 1;
q.push(to);
}
}
}
}
void dijktra (int layer)
{
priority_queue<pair<ld, int> , vector<pair<ld, int> > , greater<pair<ld, int> > > q;
for (int i = 0; i <n; i++)
{
if (reach[i] && arr[i] == 0 || i == 0) {
q.push({0.0 , i});
dist[layer][i] = 0;
}
}
if (layer > 0)
for (int c = 1; c < n; c++)
{
if (arr[c] == 2 && dist[layer-1][c] != INF)
{
q.push({dist[layer-1][c]/2 , c});
// dist[layer][c] = dist[layer-1][c]/2;
}
}
while (q.size())
{
int nod = q.top().second;
ld crtDist = q.top().first;
q.pop();
if (crtDist > dist[layer][nod]) continue;
for (auto &edg : adj[nod])
{
int to = edg.first;
ld cost = edg.second;
if (dist[layer][to] > dist[layer][nod] + cost)
{
dist[layer][to] = dist[layer][nod] + cost;
if (to != h)
q.push({dist[layer][to] , to});
}
}
}
}
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, k = K, h = H;
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]});
}
arr = _arr;
bfs();
for (int c = 0; c < n; c++)
{
dist[0][c] = INF;
}
dijktra(0);
for (int i = 1; i <= min(K , 59); i++)
{
for (int c = 0; c < n; c++)
{
dist[i][c] = INF;
}
dijktra(i);
}
for (int i = 0; i < n; i++)
{
adj[i].clear();
reach[i] = 0;
}
return (dist[min(K, 59)][h] != INF) ? dist[min(K, 59)][h] : -1;
}
