Monotone 単一始点最短路問題 (D&D Monotone Minima, in O(N (log N)^2))
(Optimization/dd_monotone_minima.hpp)

• View this file on GitHub
• Last update: 2026-11-12 11:56:29+09:00
• Include: #include "Optimization/dd_monotone_minima.hpp"

概要

Monotone Minima 法に対して、オンライン・オフライン変換を施して得られる分割統治 Monotone Minima 法。単一始点最短路問題を解く。

DP が

dp[j] = min_{i < j} (dp[i] + func(i, j))

の形で表されるとする。ここで、

g(j, i) = dp[i] + func(i, j)

が Monotone であるならば、上記の DP が分割統治 Monotone Minima 法によって、$O(N \log^{2} N)$ の計算量で DP テーブルを求めることができる。

注意点

• func(i, j) が Monotone であっても、g(j, i) = dp[i] + func(i, j) が Monotone であるとは限らない
• func(i, j) が Monge であるとき、g(j, i) = dp[i] + func(i, j) も Monge である

上記のことから、多くの場合、コストが Monge 性を満たすときに適用できるアルゴリズムであるとされる。

仕様

template<class VAL> struct DDMonotoneMinima;

構造体 DDMonotoneMinima<VAL> を宣言して、関数 solve(N, f) を呼び出す。

• 整数 N: 頂点番号が $0, 1, 2, \dots, N$ であるとする (頂点数は $N + 1$)
• 関数 f(l, r): 辺 $(l, r)$ のコストを返す関数
• 返り値: 受け取る変数を res として
  • res[v].first: 頂点 $0$ から頂点 $v$ への最短路の重み
  • res[v].second: 頂点 $0$ から頂点 $v$ への最短路において、$v$ に至る直前の頂点の番号 (存在しない場合は -1)
• また、構造体のメンバ変数にも結果が格納される
  • dp[v]: 頂点 $0$ から頂点 $v$ への最短路の重み
  • cnt[v]: 頂点 $0$ から頂点 $v$ への最短路に含まれる辺の本数
  • prev[v]: 頂点 $0$ から頂点 $v$ への最短路において、$v$ に至る直前の頂点の番号 (存在しない場合は -1)
• メンバ関数 reconstruct() を呼ぶことで、頂点 $0$ から頂点 $N$ への最短路が復元される

ランダムアクセス版

template<class FUNC> vector<pair<VAL, int>> solve(int N, const FUNC &)

• 整数 N: 頂点番号が $0, 1, 2, \dots, N$ であるとする (頂点数は $N + 1$)
• 関数 f(l, r): 辺 $(l, r)$ のコストを返す関数

スライドアクセス版

template<class ADD, class DEL, class GETCOST> vector<vector<pair<VAL, int>>> solve
(int N, const ADD &add, const DEL &del, const GETCOST &get)

• 整数 N: 頂点番号が $0, 1, 2, \dots, N$ であるとする (頂点数は $N + 1$)
• 関数 add(i): 辺 $(l, r)$ のコストが、区間 $[l, r)$ についての値に対応するとして、区間に index $i$ の分を追加するときのコストの差分を記述する関数
• 関数 del(i): 辺 $(l, r)$ のコストが、区間 $[l, r)$ についての値に対応するとして、区間から index $i$ の分を削除するときのコストの差分を記述する関数
• 関数 get(): 辺 $(l, r)$ のコストを返す関数

問題例

• AtCoder EDPC Z - Frog 3
• Codeforces Round 189 (Div. 1) C. Kalila and Dimna in the Logging Industry
• yukicoder No.705 ゴミ拾い Hard

参考文献

• tatyam: Monge の手引き書

Depends on

• Monotone 行最小値問題 (Monotone Minima, in O(H + W log H)) (Optimization/monotone_minima.hpp)

Required by

• Monge 単一始点 d-辺最短路問題 (by Alien DP) (Optimization/alien_dp.hpp)
• Monge 全部乗せ (Optimization/monge_all.hpp)
• Monge 単一始点最短路アルゴリズム群のラッパー (Optimization/monge_shortest_path.hpp)

Verified with

• tests/yukicoder/yukicoder_0409_monge_shortest_path_simple_larsch.test.cpp
• tests/yukicoder/yukicoder_0705_dd_monotone_minima.test.cpp
• tests/yukicoder/yukicoder_0705_monge_shortest_path.test.cpp
• tests/yukicoder/yukicoder_2078_monge_shortest_path_simple_larsch.test.cpp
• tests/AtCoder/ABC_218_H_alien_dp.cpp (manual)
• tests/AtCoder/EDPC_Z_dd_monotone_minima.cpp (manual)
• tests/Codeforces/Codeforces_Round_189_Div1_C_dd_monotone_minima.cpp (manual)
• tests/Codeforces/Codeforces_Round_438_Div12_F_alien_dp.cpp (manual)

Code

#pragma once
#include <bits/stdc++.h>
#include <cassert>
using namespace std;

#include "monotone_minima.hpp"

// find shortest path on DAG by D&D Monotone Minima, O(N (log N)^2)
// vertex: 0, 1, 2, ..., N
// A(j, i) = dp[i] + f(i, j) must be monotone (argmin is not decreasing)
// Attention: Even if f is monotone, A is not necessarily monotone
// slide access OK
template<class VAL> struct DDMonotoneMinima {
    VAL INF = numeric_limits<VAL>::max() / 2;
    int CNT_INF = numeric_limits<int>::max() / 2;

    // results
    vector<VAL> dp;
    vector<int> cnt, prev;

    // solver (random access ver)
    template<class FUNC> vector<pair<VAL, int>> solve(int N, const FUNC &f) {
        dp.assign(N + 1, INF);
        cnt.assign(N + 1, CNT_INF);
        prev.assign(N + 1, 0);
        dp[0] = 0, cnt[0] = 0;
        vector<pair<VAL, int>> res(N + 1, make_pair(INF, -1));
        vector<pair<VAL, int>> tmp(N + 1, make_pair(INF, -1));
        res[0].first = VAL(0);
        auto f2 = [&](int i, int j) -> VAL { return res[j].first + f(j, i); };
        auto rec = [&](auto &&rec, int left, int right) -> void {
            if (right - left <= 1) return;
            int mid = (left + right) / 2;
            rec(rec, left, mid);
            for (int i = mid; i < right; i++) tmp[i] = {INF, -1};
            MonotoneMinimaRec(mid, right, left, mid, f2, tmp);
            for (int i = mid; i < right; i++) if (tmp[i].first < res[i].first) res[i] = tmp[i];
            rec(rec, mid, right);
        };
        rec(rec, 0, N + 1);
        for (int r = 1; r <= N; r++) {
            dp[r] = res[r].first;
            prev[r] = res[r].second;
            if (prev[r] != -1) cnt[r] = cnt[prev[r]] + 1;
        }
        return res;
    }

    // solver (slide access ver)
    template<class ADD, class DEL, class GETCOST> vector<pair<VAL, int>> solve
    (int N, const ADD &add, const DEL &del, const GETCOST &get) {
        int left = 0, right = 0;
        auto f = [&](int i, int j) -> long long {
            while (left < i) del(left++);
            while (i < left) add(--left);
            while (right < j) add(right++);
            while (j < right) del(--right);
            return get();
        };
        auto f2 = [&](int i, int j) -> VAL { return (j < i ? dp[j] + f(j, i) : INF); };
        return solve(N, f2);
    }

    // reconstruct the shortest path
    vector<int> reconstruct() {
        int N = (int)dp.size() - 1;
        vector<int> path;
        for (int v = N; v > 0; v = prev[v]) path.emplace_back(v);
        path.emplace_back(0);
        reverse(path.begin(), path.end());
        return path;
    }
};

#line 2 "Optimization/dd_monotone_minima.hpp"
#include <bits/stdc++.h>
#line 4 "Optimization/dd_monotone_minima.hpp"
using namespace std;

#line 4 "Optimization/monotone_minima.hpp"
using namespace std;

// find min_j f(i, j) for all i, by Monotone Minima, O(H + W log H)
// f(i, j) must be monotone (argmin is not decreasing)
// slide access OK
template<class VAL, class FUNC> void MonotoneMinimaRec
(int HL, int HR, int WL, int WR, const FUNC &f, vector<pair<VAL, int>> &res) {
    if (HR - HL <= 0) return;
    int HM = (HL + HR) / 2;
    res[HM].second = WL;
    for (int i = WL; i < WR; i++) {
        VAL val = f(HM, i);
        if (res[HM].first > val) res[HM] = make_pair(val, i);
    }
    MonotoneMinimaRec(HL, HM, WL, res[HM].second + 1, f, res);
    MonotoneMinimaRec(HM + 1, HR, res[HM].second, WR, f, res);
}
template<class VAL, class FUNC> vector<pair<VAL, int>> MonotoneMinima(int H, int W, const FUNC &f) {
    vector<pair<VAL, int>> res(H, make_pair(numeric_limits<VAL>::max() / 2, -1));
    MonotoneMinimaRec(0, H, 0, W, f, res);
    return res;
}
#line 7 "Optimization/dd_monotone_minima.hpp"

// find shortest path on DAG by D&D Monotone Minima, O(N (log N)^2)
// vertex: 0, 1, 2, ..., N
// A(j, i) = dp[i] + f(i, j) must be monotone (argmin is not decreasing)
// Attention: Even if f is monotone, A is not necessarily monotone
// slide access OK
template<class VAL> struct DDMonotoneMinima {
    VAL INF = numeric_limits<VAL>::max() / 2;
    int CNT_INF = numeric_limits<int>::max() / 2;

    // results
    vector<VAL> dp;
    vector<int> cnt, prev;

    // solver (random access ver)
    template<class FUNC> vector<pair<VAL, int>> solve(int N, const FUNC &f) {
        dp.assign(N + 1, INF);
        cnt.assign(N + 1, CNT_INF);
        prev.assign(N + 1, 0);
        dp[0] = 0, cnt[0] = 0;
        vector<pair<VAL, int>> res(N + 1, make_pair(INF, -1));
        vector<pair<VAL, int>> tmp(N + 1, make_pair(INF, -1));
        res[0].first = VAL(0);
        auto f2 = [&](int i, int j) -> VAL { return res[j].first + f(j, i); };
        auto rec = [&](auto &&rec, int left, int right) -> void {
            if (right - left <= 1) return;
            int mid = (left + right) / 2;
            rec(rec, left, mid);
            for (int i = mid; i < right; i++) tmp[i] = {INF, -1};
            MonotoneMinimaRec(mid, right, left, mid, f2, tmp);
            for (int i = mid; i < right; i++) if (tmp[i].first < res[i].first) res[i] = tmp[i];
            rec(rec, mid, right);
        };
        rec(rec, 0, N + 1);
        for (int r = 1; r <= N; r++) {
            dp[r] = res[r].first;
            prev[r] = res[r].second;
            if (prev[r] != -1) cnt[r] = cnt[prev[r]] + 1;
        }
        return res;
    }

    // solver (slide access ver)
    template<class ADD, class DEL, class GETCOST> vector<pair<VAL, int>> solve
    (int N, const ADD &add, const DEL &del, const GETCOST &get) {
        int left = 0, right = 0;
        auto f = [&](int i, int j) -> long long {
            while (left < i) del(left++);
            while (i < left) add(--left);
            while (right < j) add(right++);
            while (j < right) del(--right);
            return get();
        };
        auto f2 = [&](int i, int j) -> VAL { return (j < i ? dp[j] + f(j, i) : INF); };
        return solve(N, f2);
    }

    // reconstruct the shortest path
    vector<int> reconstruct() {
        int N = (int)dp.size() - 1;
        vector<int> path;
        for (int v = N; v > 0; v = prev[v]) path.emplace_back(v);
        path.emplace_back(0);
        reverse(path.begin(), path.end());
        return path;
    }
};

Back to top page