Monge shortest path
(algorithm/monge_shortest_path.hpp)

• View this file on GitHub
• Last update: 2023-11-08 11:18:30+09:00
• Include: #include "algorithm/monge_shortest_path.hpp"

説明

辺の重みがMongeであるようなグラフに対して $0$ からスタートして、 $v = 0, 1, \dots, N-1$ への最短路の値を求める。 $O(N\log N)$

詳細は このブログ にある。

Required by

• Monge d-edge shortest path (algorithm/monge_d_edge_shortest_path.hpp)

Verified with

• test/aoj/aoj_3086.test.cpp

Code

#pragma once

#include <limits>
#include <vector>

namespace ebi {

template <class F, class T = decltype(std::declval<F>()(std::declval<int>(),
                                                        std::declval<int>()))>
std::vector<T> monge_shortest_path(int n, F f) {
    const T max = std::numeric_limits<T>::max();
    std::vector<int> argmin(n, 0);
    std::vector<T> dp(n, max);
    dp[0] = 0;
    auto get = [&](int i, int j) -> T {
        T val = f(j, i);
        if (val == max || dp[j] == max) return max;
        return dp[j] + val;
    };
    auto check = [&](int i, int j) -> void {
        T val = get(i, j);
        if (val < dp[i]) {
            dp[i] = val;
            argmin[i] = j;
        }
    };
    dp[n - 1] = get(n - 1, 0);
    auto dfs = [&](auto &&self, int l, int r) -> void {
        if (r - l == 1) return;
        int m = (l + r) >> 1;
        for (int i = argmin[l]; i <= argmin[r]; i++) {
            check(m, i);
        }
        self(self, l, m);
        for (int i = l + 1; i <= m; i++) {
            check(r, i);
        }
        self(self, m, r);
    };
    dfs(dfs, 0, n - 1);
    return dp;
}

}  // namespace ebi

#line 2 "algorithm/monge_shortest_path.hpp"

#include <limits>
#include <vector>

namespace ebi {

template <class F, class T = decltype(std::declval<F>()(std::declval<int>(),
                                                        std::declval<int>()))>
std::vector<T> monge_shortest_path(int n, F f) {
    const T max = std::numeric_limits<T>::max();
    std::vector<int> argmin(n, 0);
    std::vector<T> dp(n, max);
    dp[0] = 0;
    auto get = [&](int i, int j) -> T {
        T val = f(j, i);
        if (val == max || dp[j] == max) return max;
        return dp[j] + val;
    };
    auto check = [&](int i, int j) -> void {
        T val = get(i, j);
        if (val < dp[i]) {
            dp[i] = val;
            argmin[i] = j;
        }
    };
    dp[n - 1] = get(n - 1, 0);
    auto dfs = [&](auto &&self, int l, int r) -> void {
        if (r - l == 1) return;
        int m = (l + r) >> 1;
        for (int i = argmin[l]; i <= argmin[r]; i++) {
            check(m, i);
        }
        self(self, l, m);
        for (int i = l + 1; i <= m; i++) {
            check(r, i);
        }
        self(self, m, r);
    };
    dfs(dfs, 0, n - 1);
    return dp;
}

}  // namespace ebi

Back to top page