#include "cyberland.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using pid = pair<int, double>;
#define sz(x) int(x.size())
int N, M, K;
int H;
vi x, y, c, arr;
vector<pid>* edge;
//i = not halved yet, i + N = halved
vi reachable;
vector<double> dijkstra(vector<double> dist)
{
priority_queue< pair<double, int> > tbv;
for(int i = 0; i < 2*N; i++)
{
tbv.push({-dist[i], i});
}
while(!tbv.empty())
{
int u = tbv.top().second;
if(dist[u] < -tbv.top().first)
{
tbv.pop();
continue;
}
else
{
tbv.pop();
}
if(u == H || u == H+N)
continue;
for(pid vp : edge[u])
{
int v = vp.first;
if(dist[v] <= dist[u] + vp.second)
continue;
// tbv.erase({dist[v], v});
dist[v] = dist[u] + vp.second;
tbv.push({-dist[v], v});
}
}
return dist;
}
double solve(int N_, int M_, int K_, int H_, vi x_, vi y_, vi c_, vi arr_)
{
N = N_;
M = M_;
K = K_;
H = H_;
x = x_;
y = y_;
c = c_;
arr = arr_;
edge = new vector<pid>[2*N];
for(int j = 0; j < M; j++)
{
edge[x[j]].push_back({y[j], c[j]});
edge[y[j]].push_back({x[j], c[j]});
edge[N+x[j]].push_back({y[j], c[j]});
edge[N+y[j]].push_back({x[j], c[j]});
}
vector<double> dist(2*N, double(2'000'000'000) * double(M + 1));
dist[0] = 0;
reachable = vi(N, 1);
dist = dijkstra(dist);
for(int i = 0; i < N; i++)
if(arr[i] == 0 && dist[i] < double(1'500'000'000) * double(M + 1))
dist[i] = double(0);
for(int i = 0; i < N; i++)
if(dist[i] >= double(1'500'000'000) * double(M+1))
reachable[i] = 0;
K = min(K, 70);
// K = 0;
for(int k = 1; k <= K; k++)
{
dist = dijkstra(dist);
for(int i = 0; i < N; i++)
{
if(arr[i] == 2)
{
dist[i+N] = dist[i] / double(2);
dist[i] = double(2'000'000'000) * double(M + 1);
}
}
for(int i = 0; i < N; i++)
if(!reachable[i])
dist[i] = dist[i+N] = double(2'000'000'000) * double(M + 1);
}
dist = dijkstra(dist);
for(int i = 0; i < N; i++)
if(!reachable[i])
dist[i] = double(2'000'000'000) * double(M + 1);
if(!reachable[H])
return -1;
else
return dist[H];
}
