#include <bits/stdc++.h> #include "cyberland.h" using namespace std; typedef long long ll; const int N = 2e5 + 1; vector<pair<int, double>> g[N]; double d[N][31]; 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) { for (int i = 0; i < n; i++) { for(int j = 0;j <= k;j++){ d[i][j] = 1e15; } g[i].clear(); } for (int i = 0; i < m; i++) { g[x[i]].push_back({y[i], c[i]}); g[y[i]].push_back({x[i], c[i]}); } queue<int> q; vector<int> can(n,0); can[0] = 1; q.push(0); while(!q.empty()){ int v = q.front(); q.pop(); for(auto [to,w]:g[v]){ if(to == h || can[to]) continue; q.push(to); can[to] = 1; } } vector<int> vv(1, 0); set<pair<double,pair<int,int>>> st; st.insert({0,{0,0}}); d[0][0] = 0; for (int j = 0; j < n; j++) { if (!arr[j] && can[j]) { st.insert({0,{0,j}}); d[j][0] = 0; vv.push_back(j); } } while(!st.empty()){ auto [col,v] = (*st.begin()).second; st.erase({d[v][col],{col,v}}); if(v == h) continue; for(auto [to,w]:g[v]){ if(col + 1 <= k && d[to][col + 1] > (d[v][col] + w) * 1.0 / 2 && arr[to] == 2){ st.erase({d[to][col + 1],{col + 1,to}}); d[to][col + 1] = 1.0 * (d[v][col] + w) / 2; st.insert({d[to][col + 1],{col + 1,to}}); } if(d[to][col] > d[v][col] + w){ st.erase({d[to][col],{col,to}}); d[to][col] = d[v][col] + w; st.insert({d[to][col],{col,to}}); } } } double res = 1e15; for(int i = 0;i <= k;i++){ res = min(res,d[h][i]); } if(res == 1e15) res = -1; return res; } // int main() { // int T; // assert(1 == scanf("%d", &T)); // while (T--){ // int N,M,K,H; // assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H)); // std::vector<int> x(M); // std::vector<int> y(M); // std::vector<int> c(M); // std::vector<int> arr(N); // for (int i=0;i<N;i++) // assert(1 == scanf("%d", &arr[i])); // for (int i=0;i<M;i++) // assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i])); // printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr)); // } // }