#include "cyberland.h" #include <bits/stdc++.h> using namespace std; #define node tuple<double, int, int> const int nx=1e5+5, kx=70; double dp[nx][kx], p[kx]; int dsu[nx]; int find(int x) { if (dsu[x]==x) return x; return dsu[x]=find(dsu[x]); } 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) { K=min(K, 70); priority_queue<node, vector<node>, greater<node>> pq; vector<vector<pair<int, double>>> d(nx); for (int i=0; i<N; i++) dsu[i]=i; for (int i=0; i<M; i++) { d[x[i]].push_back({y[i], c[i]}); d[y[i]].push_back({x[i], c[i]}); int px=find(x[i]), py=find(y[i]); if (px!=py) dsu[px]=py; } if (find(0)!=find(H)) return -1; for (int i=0; i<N; i++) for (int j=0; j<=K; j++) dp[i][j]=DBL_MAX; p[0]=1; for (int i=1; i<K; i++) p[i]=p[i-1]/2; dp[H][0]=0; arr[0]=0; pq.push({0, H, 0}); while (!pq.empty()) { auto [cw, cl, ck]=pq.top(); //cout<<cw<<' '<<cl<<' '<<ck<<'\n'; pq.pop(); if (arr[cl]==0) return cw; for (auto [v, w]:d[cl]) { double nw=cw+w*p[ck]; if (cw+nw<dp[v][ck]) dp[v][ck]=cw+nw, pq.push({cw+nw, v, ck}); if (arr[v]==2&&ck<K&&(cw+nw)/2<dp[v][ck+1]) dp[v][ck+1]=(cw+nw)/2, pq.push({(cw+nw)/2, v, ck+1}); } } return -1; }