#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; set<pair<double, int>> st; st.emplace(0, 0); double ans = inf; while (!st.empty()) { auto it = st.begin(); int v = it->second; st.erase(it); int i = v / k; int j = v % k; if (i == h) { ans = min(ans, dist[v]); continue; } 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; st.emplace(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; st.emplace(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; st.emplace(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 */