monge グラフ上の d-辺最短路の d=1,...,N における列挙
(dp/monge-d-edge-shortest-path-enumerate.hpp)

• View this file on GitHub
• Last update: 2026-06-05 19:46:06+09:00
• Include: #include "dp/monge-d-edge-shortest-path-enumerate.hpp"

Depends on

• monotone minima (dp/monotone-minima.hpp)

Verified with

• verify/verify-yuki/yuki-0952.test.cpp

Code

#pragma once

#include <functional>
#include <type_traits>
#include <vector>
using namespace std;

#include "monotone-minima.hpp"

// 辺コストが monge である DAG の D 辺 0-N 最短路
template <typename F>
auto enumerate_monge_d_edge_shortest_path(
    int N, F&& f, long long unreached = (1LL << 62) - 1)
    -> enable_if_t<is_invocable_r_v<long long, F&, int, int>, vector<long long>> {
  using T = __int128_t;
  T INF = (T{1} << (sizeof(T) * 8 - 2)) - 1;
  vector<long long> ans(N + 1, unreached);
  vector<T> dp(N + 1, INF);
  dp[0] = 0;
  for (int d = 1; d <= N; d++) {
    vector<int> midx = monotone_minima<T>(N + 1, N + 1, [&](int j, int i) -> T {
      return i < j ? dp[i] + std::invoke(f, i, j) : INF;
    });
    for (int i = N; i >= d; i--)
      dp[i] = dp[midx[i]] + std::invoke(f, midx[i], i);
    ans[d] = dp[N];
  }
  return ans;
}

/**
 * @brief monge グラフ上の d-辺最短路の d=1,...,N における列挙
 */

#line 2 "dp/monge-d-edge-shortest-path-enumerate.hpp"

#include <functional>
#include <type_traits>
#include <vector>
using namespace std;

#line 2 "dp/monotone-minima.hpp"

#line 6 "dp/monotone-minima.hpp"
using namespace std;

// NxN 行列がある
// m_i := argmin_j (A_{i,j}) が単調増加であるときに m_i を列挙する
// f(i, j, k) :
// A[i][j] と A[i][k] を比較 (j < k が保証されている)
// A[i][j] <= A[i][k] のとき true を返す関数を入れる (等号はどちらでもよい)
template <typename F>
auto monotone_minima(int N, int M, F&& f)
    -> enable_if_t<is_invocable_r_v<bool, F&, int, int, int>, vector<int>> {
  vector<int> res(N);
  auto dfs = [&](auto rc, int is, int ie, int l, int r) -> void {
    if (is == ie) return;
    int i = (is + ie) / 2;
    int m = l;
    for (int k = l + 1; k < r; k++) {
      if (!std::invoke(f, i, m, k)) m = k;
    }
    res[i] = m;
    rc(rc, is, i, l, m + 1);
    rc(rc, i + 1, ie, m, r);
  };
  dfs(dfs, 0, N, 0, M);
  return res;
}

// NxM 行列がある
// m_i := argmin_j (A_{i,j}) が単調増加であるときに m_i を列挙する
// A(i, j) : A[i][j] を返す関数
template <typename T, typename F>
auto monotone_minima(int N, int M, F&& A)
    -> enable_if_t<is_invocable_v<F&, int, int>, vector<int>> {
  auto f = [&](int i, int j, int k) -> bool {
    return std::invoke(A, i, j) <= std::invoke(A, i, k);
  };
  return monotone_minima(N, M, f);
}

template <typename F>
auto monotone_minima(int N, int M, F&& A)
    -> enable_if_t<!is_invocable_v<F&, int, int, int> &&
                       is_invocable_v<F&, int, int>,
                   vector<int>> {
  using T = invoke_result_t<F&, int, int>;
  return monotone_minima<T>(N, M, A);
}

/**
 * @brief monotone minima
 */
#line 9 "dp/monge-d-edge-shortest-path-enumerate.hpp"

// 辺コストが monge である DAG の D 辺 0-N 最短路
template <typename F>
auto enumerate_monge_d_edge_shortest_path(
    int N, F&& f, long long unreached = (1LL << 62) - 1)
    -> enable_if_t<is_invocable_r_v<long long, F&, int, int>, vector<long long>> {
  using T = __int128_t;
  T INF = (T{1} << (sizeof(T) * 8 - 2)) - 1;
  vector<long long> ans(N + 1, unreached);
  vector<T> dp(N + 1, INF);
  dp[0] = 0;
  for (int d = 1; d <= N; d++) {
    vector<int> midx = monotone_minima<T>(N + 1, N + 1, [&](int j, int i) -> T {
      return i < j ? dp[i] + std::invoke(f, i, j) : INF;
    });
    for (int i = N; i >= d; i--)
      dp[i] = dp[midx[i]] + std::invoke(f, midx[i], i);
    ans[d] = dp[N];
  }
  return ans;
}

/**
 * @brief monge グラフ上の d-辺最短路の d=1,...,N における列挙
 */

Back to top page