#include "cyberland.h" #include <bits/stdc++.h> using namespace std; 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]); } const double inf = 1e18; k += 1; for (int i = 0; i < n * k; i++) { dist[i] = inf; lst[i] = inf; } dist[0] = 0; priority_queue<pair<double, int>> pq; pq.push({0, 0}); 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]) { 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++) { if (dist[to * k + x] != 0) { dist[to * k + x] = 0; pq.push({dist[to * k + x], to * k + x}); } } } continue; } if (dist[to * k + j] > dist[v] + w) { int nto = to * k + j; /* if (st.find({dist[nto], nto}) != st.end()) { st.erase(st.find({dist[nto], nto})); } */ 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) { int nto = to * k + j + 1; /* if (st.find({dist[nto], nto}) != st.end()) { st.erase(st.find({dist[nto], nto})); } */ 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 */