#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
// using double = long double;
class comp{
public:
bool operator()(pair<pair<double,ll>,ll> a, pair<pair<double,ll>,ll> b){
if(a.first.first == b.first.first){
if(a.second == b.second){
return a.first.second > b.first.second;
}
return a.second > b.second;
}
return a.first.first > b.first.first;
}
};
double bleh(double weight, ll p){
return weight/pow(2,p);
}
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) {
vector<vector<pair<ll,ll>>> adj(N+1); // neigjbor, weight
for(int i = 0; i < M; i++){
ll a = x[i];
ll b = y[i];
ll w = c[i];
adj[a].push_back({b,w});
adj[b].push_back({a,w});
}
bool flag = 0;
vector<bool> vis(N+1,0);
vis[0] = 1;
queue<ll> BFS_q;
BFS_q.push(0);
while(!BFS_q.empty()){
ll at = BFS_q.front();
BFS_q.pop();
for(pair<ll,ll> p : adj[at]){
ll node = p.first;
if(vis[node]) continue;
if(node == H){
flag = 1;
continue;
}
vis[node] = 1;
BFS_q.push(node);
}
}
if(not flag){
return -1;
}
// dp-esque?
// note that if K too big (over 30??) then we are within range lol
K = min(100,K);
vector<vector<double>> dists(N+1, vector<double>(K+1,1e18));
dists[H][0] = 0;
// djk
// store: dist, k, node
priority_queue<pair<pair<double,ll>,ll>, vector<pair<pair<double,ll>,ll>>, comp> pq;
pq.push({{double(0),0},H});
while(!pq.empty()){
pair<pair<double,ll>,ll> front = pq.top();
ll node = front.second;
double curDist = front.first.first;
ll k = front.first.second;
pq.pop();
if(curDist > dists[node][k]){
continue;
}
if((node == 0 or arr[node] == 0) and vis[node]){
return curDist;
}
// cerr << "ON " << node << endl;
for(pair<ll,ll> p : adj[node]){
ll neighbor = p.first;
if(!vis[neighbor]) continue;
double weight = double(p.second);
// very confusing since we're working backwards
// since divide by two divides everything that we've traversed so far (from 0),
// dividng by two will divide evertything that we WILL traverse from cyberland
// so
weight = bleh(weight,k);
double newDist = curDist + weight;
if(newDist < dists[neighbor][k]){
dists[neighbor][k] = newDist;
pq.push({{newDist,k},neighbor});
}
if(arr[node] == 2 and node != H and k < K){ // then we can also divide by two here
newDist = curDist + (weight/double(2));
if(newDist < dists[neighbor][k+1]){
dists[neighbor][k+1] = newDist;
pq.push({{newDist,k+1},neighbor});
}
}
}
}
assert(0);
}
