#pragma once
#include <cstdlib>
#include <functional>
#include <type_traits>
#include "golden-section-search.hpp"
#include "monge-shortest-path.hpp"
// 辺コストが monge である DAG の D 辺 0-N 最短路
// f : from -> to のコスト (long long)
// upper : max abs(辺数を 1 増減させたときのコストの変化)
// (内部で int128 で計算しているので upper は 1e18 でも壊れない)
template <typename F>
auto monge_d_edge_shortest_path(int N, int D, long long upper, F&& f)
-> std::enable_if_t<std::is_invocable_r_v<long long, F&, int, int>,
long long> {
using T = __int128_t;
upper = std::abs(upper);
auto dp = [&](long long x) -> T {
auto g = [&](int from, int to) -> T { return std::invoke(f, from, to) + x; };
T cost = monge_shortest_path<T>(N, g)[N];
return cost - T{1} * D * x;
};
auto [_, res] = golden_section_search<T, false>(dp, -upper, upper);
return res;
}
/**
* @brief monge グラフ上の d-辺最短路
*/
#line 2 "dp/monge-d-edge-shortest-path.hpp"
#include <cstdlib>
#include <functional>
#include <type_traits>
#line 2 "dp/golden-section-search.hpp"
#include <cassert>
#line 6 "dp/golden-section-search.hpp"
#include <utility>
using namespace std;
// reference：https://twitter.com/noshi91/status/1399003086362865673
namespace golden_section_search_impl {
using i64 = long long;
template <typename T, bool get_min, typename F>
pair<i64, T> golden_section_search_body(F& f, i64 min, i64 max) {
assert(min <= max);
i64 a = min - 1, x, b;
{
i64 s = 1, t = 2;
while (t < max - min + 2) swap(s += t, t);
x = a + t - s, b = a + t;
}
T fx = std::invoke(f, x), fy;
while (a + b != 2 * x) {
i64 y = a + b - x;
if (max < y ||
(fy = std::invoke(f, y), get_min ? fx < fy : fx > fy)) {
b = a;
a = y;
} else {
a = x;
x = y;
fx = fy;
}
}
return {x, fx};
}
// [min, max] は閉区間を入力する
template <typename T, bool get_min = true, typename F = void>
auto golden_section_search(F&& f, i64 min, i64 max)
-> enable_if_t<is_invocable_r_v<T, F&, i64>, pair<i64, T>> {
return golden_section_search_body<T, get_min>(f, min, max);
}
template <bool get_min = true, typename F>
auto golden_section_search(F&& f, i64 min, i64 max)
-> enable_if_t<is_invocable_v<F&, i64>,
pair<i64, invoke_result_t<F&, i64>>> {
using T = invoke_result_t<F&, i64>;
return golden_section_search_body<T, get_min>(f, min, max);
}
} // namespace golden_section_search_impl
using golden_section_search_impl::golden_section_search;
/*
@brief 黄金分割探索
*/
#line 2 "dp/monge-shortest-path.hpp"
#line 5 "dp/monge-shortest-path.hpp"
#include <vector>
using namespace std;
// https://noshi91.hatenablog.com/entry/2023/02/18/005856
// 辺コストが monge である DAG の 0 - i 最短路
template <typename T, typename F>
auto monge_shortest_path(int N, F&& f)
-> enable_if_t<is_invocable_r_v<T, F&, int, int>, vector<T>> {
T INF = (T{1} << (sizeof(T) * 8 - 2)) - 1;
vector<T> dp(N + 1, INF);
vector<int> x(N + 1, 0);
auto check = [&](int from, int to) {
if (from >= to) return;
T cost = std::invoke(f, from, to);
if (dp[from] + cost < dp[to]) dp[to] = dp[from] + cost, x[to] = from;
};
auto dfs = [&](auto rc, int l, int r) -> void {
if (l + 1 >= r) return;
int m = (l + r) / 2;
for (int i = x[l]; i <= x[r]; i++) check(i, m);
rc(rc, l, m);
for (int i = l + 1; i <= m; i++) check(i, r);
rc(rc, m, r);
};
dp[0] = 0, check(0, N), dfs(dfs, 0, N);
return dp;
}
/**
* @brief monge グラフ上の最短路
*/
#line 9 "dp/monge-d-edge-shortest-path.hpp"
// 辺コストが monge である DAG の D 辺 0-N 最短路
// f : from -> to のコスト (long long)
// upper : max abs(辺数を 1 増減させたときのコストの変化)
// (内部で int128 で計算しているので upper は 1e18 でも壊れない)
template <typename F>
auto monge_d_edge_shortest_path(int N, int D, long long upper, F&& f)
-> std::enable_if_t<std::is_invocable_r_v<long long, F&, int, int>,
long long> {
using T = __int128_t;
upper = std::abs(upper);
auto dp = [&](long long x) -> T {
auto g = [&](int from, int to) -> T { return std::invoke(f, from, to) + x; };
T cost = monge_shortest_path<T>(N, g)[N];
return cost - T{1} * D * x;
};
auto [_, res] = golden_section_search<T, false>(dp, -upper, upper);
return res;
}
/**
* @brief monge グラフ上の d-辺最短路
*/
monge グラフ上の d-辺最短路