library

This documentation is automatically generated by online-judge-tools/verification-helper

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Monge Shortest Path
(Algorithm/mongedp.hpp)

View this file on GitHub
Last update: 2024-04-29 21:46:51+00:00
Include: #include "Algorithm/mongedp.hpp"

Depends on

Fibonacci Search (Algorithm/fibonacci.hpp)

Code

#pragma once
#include "Algorithm/fibonacci.hpp"

template <typename T, T wmx, typename F> T MongeShortestPath(int n, F f) {
    vector<T> dp(n, wmx);
    dp[0] = 0;
    vector<int> amin(n);

    auto check = [&](int i, int j) {
        T val = dp[j] + f(j, i);
        if (chmin(dp[i], val))
            amin[i] = j;
    };
    auto rec = [&](auto &rec, int L, int R) {
        if (R - L == 1)
            return;
        int mid = (L + R) >> 1;
        rep(k, amin[L], amin[R] + 1) check(mid, k);
        rec(rec, L, mid);
        rep(k, L + 1, mid + 1) check(R, k);
        rec(rec, mid, R);
    };

    rec(rec, 0, n - 1);
    return dp.back();
}

template <typename T, T wmx, typename F>
T dEdgeMongeShortestPath(int n, int d, F f) {
    auto calc = [&](T lamb) -> T {
        T ret = MongeShortestPath<T, wmx>(
                    n, [&](int i, int j) { return f(i, j) + lamb; }) -
                lamb * d;
        return ret;
    };
    ll lambda = FibonacciSearch<ll>(-wmx * 3, wmx * 3, calc);
    return calc(lambda);
}

/**
 * @brief Monge Shortest Path
 */

#line 2 "Algorithm/fibonacci.hpp"

template <typename T, typename F, bool MINIMIZE = 1>
T FibonacciSearch(ll lb, ll rb, F f) {
    ll s = 1, t = 2;
    while (t < rb - lb + 2) {
        s += t;
        swap(s, t);
    }
    ll L = lb - 1, m1 = L + t - s, m2 = L + s;
    T v1 = f(m1), v2 = f(m2);
    while (m1 != m2) {
        t -= s;
        swap(s, t);
        if (rb < m2 or (MINIMIZE ? v1 >= v2 : v1 <= v2)) {
            m2 = m1;
            v2 = v1;
            m1 = L + t - s;
            v1 = f(m1);
        } else {
            L = m1;
            m1 = m2;
            v1 = v2;
            m2 = L + s;
            v2 = m2 <= rb ? f(m2) : v1;
        }
    }
    return m1;
}

/**
 * @brief Fibonacci Search
 */
#line 3 "Algorithm/mongedp.hpp"

template <typename T, T wmx, typename F> T MongeShortestPath(int n, F f) {
    vector<T> dp(n, wmx);
    dp[0] = 0;
    vector<int> amin(n);

    auto check = [&](int i, int j) {
        T val = dp[j] + f(j, i);
        if (chmin(dp[i], val))
            amin[i] = j;
    };
    auto rec = [&](auto &rec, int L, int R) {
        if (R - L == 1)
            return;
        int mid = (L + R) >> 1;
        rep(k, amin[L], amin[R] + 1) check(mid, k);
        rec(rec, L, mid);
        rep(k, L + 1, mid + 1) check(R, k);
        rec(rec, mid, R);
    };

    rec(rec, 0, n - 1);
    return dp.back();
}

template <typename T, T wmx, typename F>
T dEdgeMongeShortestPath(int n, int d, F f) {
    auto calc = [&](T lamb) -> T {
        T ret = MongeShortestPath<T, wmx>(
                    n, [&](int i, int j) { return f(i, j) + lamb; }) -
                lamb * d;
        return ret;
    };
    ll lambda = FibonacciSearch<ll>(-wmx * 3, wmx * 3, calc);
    return calc(lambda);
}

/**
 * @brief Monge Shortest Path
 */

library

Monge Shortest Path (Algorithm/mongedp.hpp)

Depends on

Code

Monge Shortest Path
(Algorithm/mongedp.hpp)