#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]<0?i:(ds[i]=ds_find(ds[i]));} double d[MAX_N][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; for (int i = 0; i < n; ++i) ds[i] = -1; for (int i = 0; i < m; ++i) if (ds_find(x[i])!=ds_find(y[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)if(arr[i]==0&&ds_find(i)!=ds_find(0))arr[i]=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))return 0; if (d[vv[j]][k]>c+ww[j]) { d[vv[j]][k]=c+ww[j]; pq.emplace(-d[vv[j]][k],vv[j],k); } if(arr[vv[j]]==2&&k+1<=kk) { if (d[vv[j]][k+1]>c/2+ww[j]) { d[vv[j]][k+1]=c/2+ww[j]; pq.emplace(-d[vv[j]][k+1],vv[j],k+1); } } } } return z; }