Monge Shortest Path
(dp/monge_shortest_path.hpp)

• View this file on GitHub
• Last update: 2024-05-28 22:29:53+09:00
• Include: #include "dp/monge_shortest_path.hpp"

Description

Monge な辺重みを持つ完全 DAG 上の最短距離を求める．この問題は LARSCH algorithm によって $O(N)$ 時間で解けるが，この実装ではより実装が簡単で定数倍高速な $O(N \log N)$ 時間の簡易版 LARSCH algorithm を用いている．

• vector<T> monge_shortest_path(int n, F cost)
  • 辺 $(i,j)$ の重みが $\mathrm{cost}(i,j)$ で与えられる $n$ 頂点完全 DAG の頂点 $0$ から各頂点への最短距離を返す
  • 時間計算量: $O(n \log n)$

Reference

• 簡易版 LARSCH Algorithm - noshi91のメモ
• verify: https://atcoder.jp/contests/abc355/submissions/53788299

Code

#pragma once
#include <limits>
#include <vector>

template <typename T, typename F>
std::vector<T> monge_shortest_path(int n, const F& cost) {
    const T INF = std::numeric_limits<T>::max() / 2;
    std::vector<T> dist(n, INF);
    dist[0] = 0;
    std::vector<int> amin(n);

    auto update = [&](int i, int k) {
        if (i <= k) return;
        auto nd = dist[k] + cost(k, i);
        if (nd < dist[i]) {
            dist[i] = nd;
            amin[i] = k;
        }
    };

    auto dfs = [&](auto& dfs, int l, int r) -> void {
        if (r - l == 1) return;
        int m = (l + r) / 2;
        for (int k = amin[l]; k <= amin[r]; ++k) update(m, k);
        dfs(dfs, l, m);
        for (int k = l + 1; k <= m; ++k) update(r, k);
        dfs(dfs, m, r);
    };

    dfs(dfs, 0, n - 1);
    return dist;
}

#line 2 "dp/monge_shortest_path.hpp"
#include <limits>
#include <vector>

template <typename T, typename F>
std::vector<T> monge_shortest_path(int n, const F& cost) {
    const T INF = std::numeric_limits<T>::max() / 2;
    std::vector<T> dist(n, INF);
    dist[0] = 0;
    std::vector<int> amin(n);

    auto update = [&](int i, int k) {
        if (i <= k) return;
        auto nd = dist[k] + cost(k, i);
        if (nd < dist[i]) {
            dist[i] = nd;
            amin[i] = k;
        }
    };

    auto dfs = [&](auto& dfs, int l, int r) -> void {
        if (r - l == 1) return;
        int m = (l + r) / 2;
        for (int k = amin[l]; k <= amin[r]; ++k) update(m, k);
        dfs(dfs, l, m);
        for (int k = l + 1; k <= m; ++k) update(r, k);
        dfs(dfs, m, r);
    };

    dfs(dfs, 0, n - 1);
    return dist;
}

Back to top page