monge グラフ上の d-辺最短路
(dp/monge-d-edge-shortest-path.hpp)
Depends on
Verified with
Code
#pragma once
#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 でも壊れない)
long long monge_d_edge_shortest_path(int N, int D, long long upper,
const function<long long(int, int)>& f) {
using T = __int128_t;
upper = abs(upper);
auto dp = [&](long long x) -> T {
auto g = [&](int from, int to) -> T { return 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"
#line 2 "dp/golden-section-search.hpp"
#include <cassert>
#include <functional>
#include <utility>
using namespace std;
// reference：https://twitter.com/noshi91/status/1399003086362865673
namespace golden_section_search_impl {
using i64 = long long;
// [min, max] は閉区間を入力する
template <typename T, bool get_min = true>
pair<i64, T> golden_section_search(const function<T(i64)>& 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 = f(x), fy;
while (a + b != 2 * x) {
i64 y = a + b - x;
if (max < y || (fy = f(y), get_min ? fx < fy : fx > fy)) {
b = a;
a = y;
} else {
a = x;
x = y;
fx = fy;
}
}
return {x, fx};
}
} // namespace golden_section_search_impl
using golden_section_search_impl::golden_section_search;
/*
@brief 黄金分割探索
*/
#line 2 "dp/monge-shortest-path.hpp"
#line 4 "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>
vector<T> monge_shortest_path(int N, const function<T(int, int)>& f) {
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 = 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 5 "dp/monge-d-edge-shortest-path.hpp"
// 辺コストが monge である DAG の D 辺 0-N 最短路
// f : from -> to のコスト (long long)
// upper : max abs(辺数を 1 増減させたときのコストの変化)
// (内部で int128 で計算しているので upper は 1e18 でも壊れない)
long long monge_d_edge_shortest_path(int N, int D, long long upper,
const function<long long(int, int)>& f) {
using T = __int128_t;
upper = abs(upper);
auto dp = [&](long long x) -> T {
auto g = [&](int from, int to) -> T { return 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-辺最短路
*/
Back to top page