#line 1 "main.cpp" #define PROBELM "https://yukicoder.me/problems/no/1069" #define ERROR 1e-4 #include #line 2 "/home/user/GitHub/competitive-programming-library/utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 9 "/home/user/GitHub/competitive-programming-library/graph/yen_algorithm.hpp" /** * @brief K shortest simple paths (Yen's algorithm + Dijkstra, $O(K V (E + V) \log V)$) * @param g is an adjacent list of a simple undirected graph * @return simple paths. If there are only less than K paths, return all paths in sorted order. */ template std::vector > yen_algorithm_with_dijkstra(const std::vector > > & g, int start, int goal, int k) { using namespace std; using reversed_priority_queue = priority_queue , vector >, greater > >; // trivial cases if (k == 0) return vector >(); if (start == goal) { return vector >(1, vector(1, start)); } assert (k >= 1); // prepare int n = g.size(); auto dijkstra = [&](int start, const set & removed_vertices, const set > & removed_edges) -> pair > { // dijkstra vector > dist(n, make_pair(numeric_limits::max(), -1)); reversed_priority_queue que; dist[start] = make_pair(0, -1); que.emplace(0, start); while (not que.empty()) { auto [dist_x, x] = que.top(); que.pop(); if (dist[x].first < dist_x) continue; for (auto [y, cost] : g[x]) if (not removed_vertices.count(y) and not removed_edges.count(make_pair(x, y))) { if (dist_x + cost < dist[y].first) { dist[y] = make_pair(dist_x + cost, x); que.emplace(dist_x + cost, y); } } } // reconstruct the path if (start != goal and dist[goal].second == -1) { // failure return make_pair(dist[goal].first, vector()); } vector path; for (int x = goal; x != -1; x = dist[x].second) { path.push_back(x); } reverse(ALL(path)); return make_pair(dist[goal].first, path); }; map, double> lookup; REP (i, n) { for (auto [j, cost] : g[i]) { lookup[make_pair(i, j)] = cost; } } // run Yen's algorithm vector > result; set > > que; result.push_back(dijkstra(start, set(), set >()).second); while ((int)result.size() < k) { auto & root = result.back(); T root_cost = 0; set removed_vertices; vector prefix(result.size()); iota(ALL(prefix), 0); REP (i, (int)root.size() - 1) { // remove edges used in other shortest paths from the graph set > removed_edges; vector next_prefix; for (int j : prefix) { if (i + 1 < result[j].size() and result[j][i] == root[i]) { int x = result[j][i]; int y = result[j][i + 1]; removed_edges.emplace(x, y); removed_edges.emplace(y, x); next_prefix.push_back(j); } } prefix.swap(next_prefix); // make the new path auto [spur_cost, spur] = dijkstra(root[i], removed_vertices, removed_edges); if (not spur.empty()) { vector path(i + spur.size()); copy(root.begin(), root.begin() + i, path.begin()); copy(ALL(spur), path.begin() + i); que.emplace(root_cost + spur_cost, path); if (que.size() > k - (int)result.size()) { que.erase(prev(que.end())); } } // remove vertices in root from the graph if (root[i] != start) { removed_vertices.insert(root[i]); } root_cost += lookup[make_pair(root[i], root[i + 1])]; } // found i-th smallest path if (que.empty()) { return result; } result.push_back(que.begin()->second); que.erase(que.begin()); } return result; } #line 6 "main.cpp" using namespace std; int main() { // input int n, m, k; scanf("%d%d%d", &n, &m, &k); int start, goal; scanf("%d%d", &start, &goal); -- start; -- goal; vector x(n), y(n); REP (i, n) { scanf("%lld%lld", &x[i], &y[i]); } vector > > g(n); REP (i, m) { int p, q; cin >> p >> q; -- p; -- q; double cost = sqrt(pow(x[p] - x[q], 2) + pow(y[p] - y[q], 2)); g[p].emplace_back(q, cost); g[q].emplace_back(p, cost); } // solve auto path = yen_algorithm_with_dijkstra(g, start, goal, k); vector cost(k, -1); map, double> lookup; REP (i, n) { for (auto [j, cost] : g[i]) { lookup[make_pair(i, j)] = cost; } } REP (i, path.size()) { cost[i] = 0; REP (j, (int)path[i].size() - 1) { cost[i] += lookup[make_pair(path[i][j], path[i][j + 1])]; } } // output REP (i, k) { printf("%.12lf\n", cost[i]); } return 0; }