Monge 単一始点最短路問題 (by noshi's 簡易 LARSCH 法, in O(N log N))
(Optimization/simple_larsch.hpp)

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

概要

DP が

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

の形で表されるとする。ここで、func(i, j) が Monge であるとき、

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

も Monge であり、上記の DP は、noshi’s 簡易 LARSCH 法を用いて $O(N \log N)$ の計算量で実行できる。

LARSCH 法との比較

上記の DP は、func(i, j)が Monge であるとき、LARSCH 法によって $O(N)$ の計算量でも実行できることが知られているが、これは大変複雑である。 noshi’s 簡易 LARSCH 法は、LARSCH 法から “Reduce” Step を抜いたものである。

• LARSCH 法
  • メリット
    • 計算量が $O(N)$ とよい
  • デメリット
    • 実装が複雑
    • 辺コスト f(i, j) がスライドアクセスによってのみ高速に計算できる場合に対応できない
• noshi’s 簡易 LARSCH 法
  • メリット
    • 実装が簡単
    • 辺コスト f(i, j) がスライドアクセスによってのみ高速に計算できる場合にも対応できる
  • デメリット
    • 計算量が $O(N \log N)$ と、LARSCH 法と比較すると若干悪い

仕様

template<class VAL> struct SimpleLARSCH;

構造体 SimpleLARSCH<VAL> を宣言して、関数 solve(N, f) を適用する。

• 関数 solve() の返り値: 受け取る変数を 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 &f, bool minimize_cnt = true)

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

スライドアクセス版

template<class STATE, class ADD, class DEL, class GETCOST> vector<pair<VAL, int>> solve
(int N, const STATE &ini, const ADD &add, const DEL &del, const GETCOST &get, bool minimize_cnt = true)

• テンプレート型 STATE: 辺 $(l, r)$ に対応する区間 $[l, r)$ についての情報をまとめた構造体の型
• 整数 N: 頂点番号が $0, 1, 2, \dots, N$ であるとする (頂点数は $N + 1$)
• STATE 型変数 ini: 幅のない区間に対応する値
• 関数 add(st, i): 辺 $(l, r)$ のコストが、区間 $[l, r)$ についての値に対応するとして、区間に index $i$ の分を追加するときの STATE 型変数 st の変化を記述する関数
• 関数 del(st, i): 辺 $(l, r)$ のコストが、区間 $[l, r)$ についての値に対応するとして、区間から index $i$ の分を削除するときの STATE 型変数 st の変化を記述する関数
• 関数 get(st): 辺 $(l, r)$ のコストが、区間 $[l, r)$ についての値に対応するとして、区間の情報を表す STATE 型変数 st から辺コスト $f(l, r)$ を得るための関数

区間ウィンドウ $[l, r)$ についての情報をまとめた構造体 STATE が必要になるのは、 noshi’s 簡易 LARSCH 法の内部では、2 つのウィンドウを管理するためである。 内部で 2 つのウィンドウに対応する情報を複製して管理している。

問題例

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

参考文献

• tatyam: Monge の手引き書
• noshi: 簡易版 LARSCH Algorithm

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_monge_shortest_path.test.cpp
• tests/yukicoder/yukicoder_0705_simple_larsch.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_simple_larsch.cpp (manual)
• tests/Codeforces/Codeforces_Round_189_Div1_C_simple_larsch.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;

// noshi's simplified LARSCH
// find shortest path from vertex 0 on DAG in O(N log N)
// vertex: 0, 1, 2, ..., N
// f(i, j) must be Monge (Then, A(j, i) = dp[i] + f(i, j) is also Monge)
// slide access OK
template<class VAL> struct SimpleLARSCH {
    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, bool minimize_cnt = true) {
        dp.assign(N + 1, INF);
        cnt.assign(N + 1, CNT_INF);
        prev.assign(N + 1, 0);
        dp[0] = 0, cnt[0] = 0;

        auto relax = [&](int l, int r) -> void {
            VAL val = dp[l] + f(l, r);
            int cn = cnt[l] + 1;
            if (dp[r] > val || (dp[r] == val && (minimize_cnt ? cn < cnt[r] : cn > cnt[r]))) {
                dp[r] = val;
                cnt[r] = cn;
                prev[r] = l;
            }
        };
        auto rec = [&](auto &&rec, int l, int r) -> void {
            if (r - l <= 1) return;
            int m = (l + r) / 2;
            for (int k = prev[l]; k <= prev[r]; k++) relax(k, m);
            rec(rec, l, m);
            for (int k = l + 1; k <= m; k++) relax(k, r);
            rec(rec, m, r);
        };

        if (N > 0) relax(0, N), rec(rec, 0, N);
        vector<pair<VAL, int>> res(N + 1, make_pair(numeric_limits<VAL>::max() / 2, -1));
        res[0].first = VAL(0);
        for (int i = 1; i <= N; i++) res[i] = {dp[i], prev[i]};
        return res;
    }

    // solver (slide access ver)
    template<class STATE, class ADD, class DEL, class GETCOST> vector<pair<VAL, int>> solve
    (int N, const STATE &ini, const ADD &add, const DEL &del, const GETCOST &get, bool minimize_cnt = true) {
        dp.assign(N + 1, INF);
        cnt.assign(N + 1, CNT_INF);
        prev.assign(N + 1, 0);
        dp[0] = 0, cnt[0] = 0;

        STATE win[2] = { ini, ini };
        int cl[2] = {0, 0}, cr[2] = {0, 0};

        auto move_cursor = [&](int c, int l, int r) {
            while (cr[c] < r) add(win[c], cr[c]++);
            while (cl[c] > l) add(win[c], --cl[c]);
            while (cr[c] > r) del(win[c], --cr[c]);
            while (cl[c] < l) del(win[c], cl[c]++);
        };
        auto relax = [&](int c, int l, int r) {
            move_cursor(c, l, r);
            VAL val = dp[l] + get(win[c]);
            int cn = cnt[l] + 1;
            if (dp[r] > val || (dp[r] == val && (minimize_cnt ? cn < cnt[r] : cn > cnt[r]))) {
                dp[r] = val;
                cnt[r] = cn;
                prev[r] = l;
            }
        };
        auto rec = [&](auto &&rec, int l, int r) -> void {
            if (r - l <= 1) return;
            int m = (l + r) / 2;
            for (int k = prev[l]; k <= prev[r]; k++) relax(0, k, m);
            rec(rec, l, m);
            for (int k = l + 1; k <= m; k++) relax(1, k, r);
            rec(rec, m, r);
        };

        if (N > 0) relax(0, 0, N), rec(rec, 0, N);
        vector<pair<VAL, int>> res(N + 1, make_pair(numeric_limits<VAL>::max() / 2, -1));
        res[0].first = VAL(0);
        for (int i = 1; i <= N; i++) res[i] = {dp[i], prev[i]};
        return res;
    }

    // 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/simple_larsch.hpp"
#include <bits/stdc++.h>
#line 4 "Optimization/simple_larsch.hpp"
using namespace std;

// noshi's simplified LARSCH
// find shortest path from vertex 0 on DAG in O(N log N)
// vertex: 0, 1, 2, ..., N
// f(i, j) must be Monge (Then, A(j, i) = dp[i] + f(i, j) is also Monge)
// slide access OK
template<class VAL> struct SimpleLARSCH {
    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, bool minimize_cnt = true) {
        dp.assign(N + 1, INF);
        cnt.assign(N + 1, CNT_INF);
        prev.assign(N + 1, 0);
        dp[0] = 0, cnt[0] = 0;

        auto relax = [&](int l, int r) -> void {
            VAL val = dp[l] + f(l, r);
            int cn = cnt[l] + 1;
            if (dp[r] > val || (dp[r] == val && (minimize_cnt ? cn < cnt[r] : cn > cnt[r]))) {
                dp[r] = val;
                cnt[r] = cn;
                prev[r] = l;
            }
        };
        auto rec = [&](auto &&rec, int l, int r) -> void {
            if (r - l <= 1) return;
            int m = (l + r) / 2;
            for (int k = prev[l]; k <= prev[r]; k++) relax(k, m);
            rec(rec, l, m);
            for (int k = l + 1; k <= m; k++) relax(k, r);
            rec(rec, m, r);
        };

        if (N > 0) relax(0, N), rec(rec, 0, N);
        vector<pair<VAL, int>> res(N + 1, make_pair(numeric_limits<VAL>::max() / 2, -1));
        res[0].first = VAL(0);
        for (int i = 1; i <= N; i++) res[i] = {dp[i], prev[i]};
        return res;
    }

    // solver (slide access ver)
    template<class STATE, class ADD, class DEL, class GETCOST> vector<pair<VAL, int>> solve
    (int N, const STATE &ini, const ADD &add, const DEL &del, const GETCOST &get, bool minimize_cnt = true) {
        dp.assign(N + 1, INF);
        cnt.assign(N + 1, CNT_INF);
        prev.assign(N + 1, 0);
        dp[0] = 0, cnt[0] = 0;

        STATE win[2] = { ini, ini };
        int cl[2] = {0, 0}, cr[2] = {0, 0};

        auto move_cursor = [&](int c, int l, int r) {
            while (cr[c] < r) add(win[c], cr[c]++);
            while (cl[c] > l) add(win[c], --cl[c]);
            while (cr[c] > r) del(win[c], --cr[c]);
            while (cl[c] < l) del(win[c], cl[c]++);
        };
        auto relax = [&](int c, int l, int r) {
            move_cursor(c, l, r);
            VAL val = dp[l] + get(win[c]);
            int cn = cnt[l] + 1;
            if (dp[r] > val || (dp[r] == val && (minimize_cnt ? cn < cnt[r] : cn > cnt[r]))) {
                dp[r] = val;
                cnt[r] = cn;
                prev[r] = l;
            }
        };
        auto rec = [&](auto &&rec, int l, int r) -> void {
            if (r - l <= 1) return;
            int m = (l + r) / 2;
            for (int k = prev[l]; k <= prev[r]; k++) relax(0, k, m);
            rec(rec, l, m);
            for (int k = l + 1; k <= m; k++) relax(1, k, r);
            rec(rec, m, r);
        };

        if (N > 0) relax(0, 0, N), rec(rec, 0, N);
        vector<pair<VAL, int>> res(N + 1, make_pair(numeric_limits<VAL>::max() / 2, -1));
        res[0].first = VAL(0);
        for (int i = 1; i <= N; i++) res[i] = {dp[i], prev[i]};
        return res;
    }

    // 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