#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
struct edge
{
int ver, div;
double cost;
edge(int _ver = 0, int _div = 0, double _cost = 0)
{
ver = _ver;
div = _div;
cost = _cost;
}
bool operator < (const edge &e) const
{
///cout << "compare " << cost << " " << div << " " << e.cost << " " << e.div << endl;
if (div > e.div)
return true;
if (div < e.div)
return false;
return cost > e.cost;
}
};
const int maxk = 101;
const double inf = 1e18;
const double eps = 1e-7;
vector < pair < int, ll > > adj[maxn];
double dp[maxk][maxn];
int used[maxk][maxn];
int can_get[maxn];
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
if (K > 100) /// fix to 60
K = 100;
for (int i = 0; i < N; i ++)
adj[i].clear(), can_get[i] = 0;
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]});
}
queue < int > tmp;
tmp.push(0);
can_get[0] = 1;
while(!tmp.empty())
{
int cur = tmp.front();
tmp.pop();
for (pair < int, ll > nb : adj[cur])
{
if (!can_get[nb.first] && nb.first != H)
{
can_get[nb.first] = 1;
tmp.push(nb.first);
}
}
}
priority_queue < edge > q;
for (int j = 0; j <= K; j ++)
for (int i = 0; i < N; i ++)
{
used[j][i] = 0;
dp[j][i] = inf;
}
dp[0][0] = 0;
q.push(edge(0, 0, 0));
for (int i = 0; i < N; i ++)
{
if (can_get[i] && arr[i] == 0)
q.push(edge(i, 0, 0)), dp[0][i] = 0;
}
///for (int cnt = 0; cnt <= K)
while(!q.empty())
{
edge cur = q.top();
q.pop();
///cout << q.size() << endl;
///cout << cur.ver << " " << cur.div << " " << cur.cost << endl;
//cout << used[cur.div][cur.ver] << endl;
if (used[cur.div][cur.ver])
continue;
used[cur.div][cur.ver] = 1;
if (cur.ver == H)
continue;
///cout << adj[cur.ver].size() << endl;
for (pair < int, ll > nb : adj[cur.ver])
{
edge to(nb.first, cur.div, cur.cost + nb.second);
///cout << "here " << to.ver << " : " << to.cost << endl;
if (to.cost + eps < dp[to.div][to.ver])
{
///cout << "YEP " << " ? " << endl;
dp[to.div][to.ver] = to.cost;
q.push(to);
}
if (arr[to.ver] == 2 && to.div < K)
{
to.cost = to.cost / 2.0;
to.div ++;
if (to.cost + eps < dp[to.div][to.ver])
{
dp[to.div][to.ver] = to.cost;
q.push(to);
}
}
}
}
double ans = inf;
for (int j = 0; j <= K; j ++)
ans = min(ans, dp[j][H]);
if (ans > 1e16)
return -1;
return ans;
}
