dijkstra() (ダイクストラ, $O((V + E)\log V)$)
(Graph/Shortest-Path/dijkstra.hpp)

#pragma once
#include <cassert>
#include <functional>
#include <queue>
#include <type_traits>
#include <utility>
#include <vector>

#include "../../Util/at.hpp"
#include "../../Util/chminmax.hpp"
#include "../../Util/int-infinity.hpp"

/**
 * @brief dijkstra() (ダイクストラ, $O((V + E)\log V)$)
 *
 * @param dist:
 *      start からの距離を格納する配列。
 *      要素数は頂点数以上でなければならない。INFなどのでかい値でfillされている必要がある。
 *      多次元配列でもOK。
 *
 * @param start:
 *      頂点を表すdistの添字。
 *      distが一次元配列なら整数型,
 *      distが二次元配列ならstd::pair<integer, integer> または std::tuple<integer, integer> または std::array<integer, 2>,
 *      distが三次元配列ならstd::tuple<integer, integer, integer> または std::array<integer, 3>。
 *      start = {i, j, k} のとき dist[i][j][k] でアクセスする。
 *
 * @param enumerateNextVertex:
 *      fn(from: Vertex, fn(to: Vertex, w: EdgeWeight) => void) => void
 *      第一引数にVertex, 第二引数に関数をとる関数。
 *      この関数が第一引数の頂点fromから次の頂点の遷移先を列挙し、第二引数に渡すことで dijkstra() に遷移処理を委譲する。
 */
template <class DistArray, class Vertex, class NextVertexEnumerator>
DistArray dijkstra(DistArray&& dist, Vertex start, NextVertexEnumerator enumerateNextVertex) {
    using arumakan::at;
    assert(!dist.empty());
    assert(at(dist, start) >= INF);
    using WeightType = typename std::remove_reference_t<decltype(at(dist, start))>;
    using P = std::pair<WeightType, Vertex>;

    std::priority_queue<P, std::vector<P>, std::greater<P>> que;
    que.emplace(at(dist, start) = WeightType(), start);

    while (!que.empty()) {
        const auto curDist = que.top().first;
        const auto curVertex = que.top().second;
        que.pop();
        if (at(dist, curVertex) < curDist) continue;
        enumerateNextVertex(curVertex, [&](auto nxtVertex, auto edgeWeight) {
            if (chmin(at(dist, nxtVertex), curDist + edgeWeight)) {
                que.emplace(curDist + edgeWeight, nxtVertex);
            }
        });
    }
    return dist;
}

#line 2 "Graph/Shortest-Path/dijkstra.hpp"
#include <cassert>
#include <functional>
#include <queue>
#include <type_traits>
#include <utility>
#include <vector>

#line 2 "Util/at.hpp"
#include <tuple>
#line 5 "Util/at.hpp"

/**
 * @brief at() ()
 */
namespace arumakan {

//! at(a, i) returns a[i]
template <class Array, class Integer, std::enable_if_t<std::is_integral<Integer>::value, std::nullptr_t> = nullptr>
inline auto at(Array&& a, Integer i) -> decltype(a[0])& {
    return a[i];
}

//! at(a, Tuple{i}) returns a[i]
template <class Array, class Tuple, std::enable_if_t<std::tuple_size<Tuple>::value == 1, std::nullptr_t> = nullptr>
inline auto at(Array&& a, Tuple index) -> decltype(a[0])& {
    return a[std::get<0>(index)];
}

//! at(mat, Tuple{y, x}) returns mat[y][x]
template <class Matrix, class Tuple, std::enable_if_t<std::tuple_size<Tuple>::value == 2, std::nullptr_t> = nullptr>
inline auto at(Matrix&& mat, Tuple index) -> decltype(mat[0][0])& {
    return mat[std::get<0>(index)][std::get<1>(index)];
}

//! at(cube, Tuple{z, y, x}) returns cube[z][y][x]
template <class Cube, class Tuple, std::enable_if_t<std::tuple_size<Tuple>::value == 3, std::nullptr_t> = nullptr>
inline auto at(Cube&& cube, Tuple index) -> decltype(cube[0][0][0])& {
    return cube[std::get<0>(index)][std::get<1>(index)][std::get<2>(index)];
}

}  // namespace arumakan
#line 2 "Util/chminmax.hpp"

/**
 * @brief chmin(), chmax()
 */
template <class T, class U>
inline bool chmin(T& a, const U& b) {
    return b < a && (a = b, true);
}

template <class T, class U>
inline bool chmax(T& a, const U& b) {
    return b > a && (a = b, true);
}
#line 2 "Util/int-infinity.hpp"
#include <cstdint>

/**
 * @brief int-infinity (整数のデカイ値)
 * 2倍してもオーバーフローしない & memset()にも使える (需要ある？)
 */
constexpr int32_t INF = 0x3f3f3f3f;
constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
#line 12 "Graph/Shortest-Path/dijkstra.hpp"

/**
 * @brief dijkstra() (ダイクストラ, $O((V + E)\log V)$)
 *
 * @param dist:
 *      start からの距離を格納する配列。
 *      要素数は頂点数以上でなければならない。INFなどのでかい値でfillされている必要がある。
 *      多次元配列でもOK。
 *
 * @param start:
 *      頂点を表すdistの添字。
 *      distが一次元配列なら整数型,
 *      distが二次元配列ならstd::pair<integer, integer> または std::tuple<integer, integer> または std::array<integer, 2>,
 *      distが三次元配列ならstd::tuple<integer, integer, integer> または std::array<integer, 3>。
 *      start = {i, j, k} のとき dist[i][j][k] でアクセスする。
 *
 * @param enumerateNextVertex:
 *      fn(from: Vertex, fn(to: Vertex, w: EdgeWeight) => void) => void
 *      第一引数にVertex, 第二引数に関数をとる関数。
 *      この関数が第一引数の頂点fromから次の頂点の遷移先を列挙し、第二引数に渡すことで dijkstra() に遷移処理を委譲する。
 */
template <class DistArray, class Vertex, class NextVertexEnumerator>
DistArray dijkstra(DistArray&& dist, Vertex start, NextVertexEnumerator enumerateNextVertex) {
    using arumakan::at;
    assert(!dist.empty());
    assert(at(dist, start) >= INF);
    using WeightType = typename std::remove_reference_t<decltype(at(dist, start))>;
    using P = std::pair<WeightType, Vertex>;

    std::priority_queue<P, std::vector<P>, std::greater<P>> que;
    que.emplace(at(dist, start) = WeightType(), start);

    while (!que.empty()) {
        const auto curDist = que.top().first;
        const auto curVertex = que.top().second;
        que.pop();
        if (at(dist, curVertex) < curDist) continue;
        enumerateNextVertex(curVertex, [&](auto nxtVertex, auto edgeWeight) {
            if (chmin(at(dist, nxtVertex), curDist + edgeWeight)) {
                que.emplace(curDist + edgeWeight, nxtVertex);
            }
        });
    }
    return dist;
}