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