#include "cyberland.h" #include <tuple> #include <vector> #include <queue> #include <utility> #define MAX_N 100001 #define MAX_M 200001 #define MAX_K 71 int head[MAX_N], nxt[MAX_M], vv[MAX_M]; int ds[MAX_N]; int ds_find(int i){return ds[i]==i?i:(ds[i]=ds_find(ds[i]));} double ww[MAX_M],d[MAX_N][MAX_K],p2[MAX_K]; int i = 1; void link(int u, int v, int w) { nxt[i] = head[u]; vv[i] = v; ww[i] = w; head[u] = i++; } double solve(int n, int m, int kk, 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)head[i]=0,ds[i]=i; i=1; p2[0]=1;for(int j=1;j<MAX_K;++j)p2[j]=p2[j-1]/2; if (kk >= MAX_K) kk = MAX_K - 1; for (int i = 0; i < m; ++i) ds[ds_find(y[i])]=ds_find(x[i]), link(x[i], y[i], c[i]), link(y[i], x[i], c[i]); for (int i = 0; i < n; ++i) for (int j = 0; j <= kk; ++j) d[i][j] = 1e18; arr[0]=0; using T = std::tuple<double, int, int>; std::priority_queue<T, std::vector<T>, std::greater<T> >pq; auto nq = [&](double cost, int u, int k) { if (cost<d[u][k])d[u][k]=cost,pq.emplace(-cost,u,k); }; nq(0,h,0); while (pq.size()) { auto[c,u,k]=pq.top();pq.pop(); if (d[u][k]!=c)continue; if(ds_find(u)==ds_find(0)&&arr[u]==0)return c; for(int j=head[u];j;j=nxt[j]) { int v=vv[j]; double w=ww[j]; nq(c+w*p2[k], v, k); if(arr[v]==2&&k<kk) nq(c+w*p2[k],v,k+1); } } return -1; }