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