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

• View this file on GitHub
• Last update: 2023-12-28 15:52:36+09:00
• Include: #include "algorithm/monge_d_edge_shortest_path.hpp"

説明

辺の重みがMongeであるようなグラフに対して $0$ からスタートして、 $N-1$ へちょうど $d$ 辺使った場合の最短路の値を求める。 $O(N\log N \log (\max))$ 。 $\max$ は $1$ 辺の最大長。

reference: Mongeグラフ上のd-辺最短路長を計算するアルゴリズム

Depends on

• Golden section search (algorithm/golden_section_search.hpp)
• Monge shortest path (algorithm/monge_shortest_path.hpp)
• template/int_alias.hpp

Code

#pragma once

#include <utility>

#include "../algorithm/golden_section_search.hpp"
#include "../algorithm/monge_shortest_path.hpp"

namespace ebi {

template <std::integral S, class F,
          class T = decltype(std::declval<F>()(std::declval<int>(),
                                               std::declval<int>()))>
T monge_d_edge_shortest_path(int n, int d, S upper, F f) {
    auto dp = [&](S x) -> T {
        auto g = [&](int i, int j) -> T { return f(i, j) + x; };
        T c = monge_shortest_path(n, g)[n - 1];
        return c - T(1) * x * d;
    };
    return golden_section_search(dp, -upper, upper, std::greater<T>()).second;
}

}  // namespace ebi

#line 2 "algorithm/monge_d_edge_shortest_path.hpp"

#include <utility>

#line 2 "algorithm/golden_section_search.hpp"

#include <cassert>
#include <concepts>
#include <functional>
#line 7 "algorithm/golden_section_search.hpp"

#line 2 "template/int_alias.hpp"

#include <cstdint>

namespace ebi {

using ld = long double;
using std::size_t;
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;

}  // namespace ebi
#line 9 "algorithm/golden_section_search.hpp"

namespace ebi {

// ref: https://x.com/noshi91/status/1399003086362865673
template <std::integral S, class F,
          class T = decltype(std::declval<F>()(std::declval<S>())),
          class Compare = std::less<T>>
std::pair<S, T> golden_section_search(F f, S min, S max,
                                      const Compare &compare = Compare()) {
    assert(min <= max);
    S a = min - 1, x, b;
    {
        S s = 1, t = 2;
        while (t < max - min + 2) {
            std::swap(s += t, t);
        }
        x = a + t - s;
        b = a + t;
    }
    T fx = f(x), fy;
    while (a + b != 2 * x) {
        S y = a + b - x;
        if (max < y || compare(fx, (fy = f(y)))) {
            b = a;
            a = y;
        } else {
            a = x;
            x = y;
            fx = fy;
        }
    }
    return {x, fx};
}

}  // 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
#line 7 "algorithm/monge_d_edge_shortest_path.hpp"

namespace ebi {

template <std::integral S, class F,
          class T = decltype(std::declval<F>()(std::declval<int>(),
                                               std::declval<int>()))>
T monge_d_edge_shortest_path(int n, int d, S upper, F f) {
    auto dp = [&](S x) -> T {
        auto g = [&](int i, int j) -> T { return f(i, j) + x; };
        T c = monge_shortest_path(n, g)[n - 1];
        return c - T(1) * x * d;
    };
    return golden_section_search(dp, -upper, upper, std::greater<T>()).second;
}

}  // namespace ebi

Back to top page