#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]; bool can[nx]; 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); vector<vector<double>> dp(N, vector<double>(K, DBL_MAX)); queue<int> q; for (int i=0; i<N; i++) can[i]=0; 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]}); } q.push(0); while (!q.empty()) { int x=q.front(); can[x]=1; q.pop(); if (x==H) continue; for (auto [y, z]:d[x]) if (!can[y]) q.push(y); } if (!can[H]) return -1; 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(); pq.pop(); if (arr[cl]==0) return cw; for (auto [v, w]:d[cl]) { if (!can[v]||v==H) continue; double nw=cw+w*p[ck]; if (nw<dp[v][ck]) dp[v][ck]=nw, pq.push({nw, v, ck}); if (arr[v]==2&&ck<K&&nw<dp[v][ck+1]) dp[v][ck+1]=nw, pq.push({nw, v, ck+1}); } } return -1; }