This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "algorithm/monge_d_edge_shortest_path.hpp"
辺の重みがMongeであるようなグラフに対して $0$ からスタートして、 $N-1$ へちょうど $d$ 辺使った場合の最短路の値を求める。 $O(N\log N \log (\max))$ 。 $\max$ は $1$ 辺の最大長。
reference: Mongeグラフ上のd-辺最短路長を計算するアルゴリズム
#pragma once #include <utility> #include "../algorithm/golden_section_search.hpp" #include "../algorithm/monge_shortest_path.hpp" namespace ebi { template <std::integral S, class F, class T = decltype(std::declval<F>()(std::declval<int>(), std::declval<int>()))> T monge_d_edge_shortest_path(int n, int d, S upper, F f) { auto dp = [&](S x) -> T { auto g = [&](int i, int j) -> T { return f(i, j) + x; }; T c = monge_shortest_path(n, g)[n - 1]; return c - T(1) * x * d; }; return golden_section_search(dp, -upper, upper, std::greater<T>()).second; } } // namespace ebi
#line 2 "algorithm/monge_d_edge_shortest_path.hpp" #include <utility> #line 2 "algorithm/golden_section_search.hpp" #include <cassert> #include <concepts> #include <functional> #line 7 "algorithm/golden_section_search.hpp" #line 2 "template/int_alias.hpp" #include <cstdint> namespace ebi { using ld = long double; using std::size_t; using i8 = std::int8_t; using u8 = std::uint8_t; using i16 = std::int16_t; using u16 = std::uint16_t; using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; } // namespace ebi #line 9 "algorithm/golden_section_search.hpp" namespace ebi { // ref: https://x.com/noshi91/status/1399003086362865673 template <std::integral S, class F, class T = decltype(std::declval<F>()(std::declval<S>())), class Compare = std::less<T>> std::pair<S, T> golden_section_search(F f, S min, S max, const Compare &compare = Compare()) { assert(min <= max); S a = min - 1, x, b; { S s = 1, t = 2; while (t < max - min + 2) { std::swap(s += t, t); } x = a + t - s; b = a + t; } T fx = f(x), fy; while (a + b != 2 * x) { S y = a + b - x; if (max < y || compare(fx, (fy = f(y)))) { b = a; a = y; } else { a = x; x = y; fx = fy; } } return {x, fx}; } } // namespace ebi #line 2 "algorithm/monge_shortest_path.hpp" #include <limits> #include <vector> namespace ebi { template <class F, class T = decltype(std::declval<F>()(std::declval<int>(), std::declval<int>()))> std::vector<T> monge_shortest_path(int n, F f) { const T max = std::numeric_limits<T>::max(); std::vector<int> argmin(n, 0); std::vector<T> dp(n, max); dp[0] = 0; auto get = [&](int i, int j) -> T { T val = f(j, i); if (val == max || dp[j] == max) return max; return dp[j] + val; }; auto check = [&](int i, int j) -> void { T val = get(i, j); if (val < dp[i]) { dp[i] = val; argmin[i] = j; } }; dp[n - 1] = get(n - 1, 0); auto dfs = [&](auto &&self, int l, int r) -> void { if (r - l == 1) return; int m = (l + r) >> 1; for (int i = argmin[l]; i <= argmin[r]; i++) { check(m, i); } self(self, l, m); for (int i = l + 1; i <= m; i++) { check(r, i); } self(self, m, r); }; dfs(dfs, 0, n - 1); return dp; } } // namespace ebi #line 7 "algorithm/monge_d_edge_shortest_path.hpp" namespace ebi { template <std::integral S, class F, class T = decltype(std::declval<F>()(std::declval<int>(), std::declval<int>()))> T monge_d_edge_shortest_path(int n, int d, S upper, F f) { auto dp = [&](S x) -> T { auto g = [&](int i, int j) -> T { return f(i, j) + x; }; T c = monge_shortest_path(n, g)[n - 1]; return c - T(1) * x * d; }; return golden_section_search(dp, -upper, upper, std::greater<T>()).second; } } // namespace ebi