#include "cyberland.h" #include <bits/stdc++.h> using namespace std; const double eps = 1e-8; const int MAX = 100010; vector<pair<int, int>> g[MAX]; double dist[MAX * 72]; double lst[MAX * 72]; 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> a) { k = min(k, 68); for (int i = 0; i < n; i++) { g[i].clear(); } for (int i = 0; i < m; i++) { g[x[i]].emplace_back(y[i], c[i]); g[y[i]].emplace_back(x[i], c[i]); } vector<int> que(1, 0); vector<bool> was(n, false); was[0] = true; for (int b = 0; b < (int) que.size(); b++) { int i = que[b]; for (auto& p : g[i]) { int j = p.first; if (!was[j]) { was[j] = true; que.push_back(j); } } } const double inf = 1e15; k += 1; for (int i = 0; i < n * k; i++) { dist[i] = inf; lst[i] = inf; } priority_queue<pair<double, int>> pq; for (int j : que) { if (j == h) { continue; } if (j == 0 || a[j] == 0) { for (int x = 0; x < k; x++) { dist[j * k + x] = 0; pq.push({dist[j * k + x], j * k + x}); } } } double ans = inf; while (!pq.empty()) { auto it = pq.top(); int v = it.second; pq.pop(); int i = v / k; int j = v % k; if (i == h) { ans = min(ans, dist[v]); continue; } if (lst[v] <= dist[v] + eps) { continue; } lst[v] = dist[v]; for (auto& p : g[i]) { int to = p.first; int w = p.second; if (a[to] == 0) { if (dist[to * k + j] > 0) { for (int x = 0; x < k; x++) { dist[to * k + x] = 0; pq.push({dist[to * k + x], to * k + x}); } } continue; } if (dist[to * k + j] > dist[v] + w + eps) { int nto = to * k + j; dist[nto] = dist[v] + w; pq.push({-dist[nto], nto}); } if (a[to] == 2) { if (j + 1 < k && dist[to * k + j + 1] > (dist[v] + w) / 2.000000 + eps) { int nto = to * k + j + 1; dist[nto] = (dist[v] + w) / 2.000000; pq.push({-dist[nto], nto}); } } } } if (ans == inf) { ans = -1; } return ans; } /* 1 3 2 30 2 1 2 1 1 2 12 2 0 4 4.00000000000 1 4 4 30 3 1 0 2 1 0 1 5 0 2 4 1 3 2 2 3 4 2.00000000000 */