bfs() (幅優先探索による単一始点最短経路, 次元拡張に対応)
(Graph/Shortest-Path/bfs.hpp)

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

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

/**
 * @brief bfs() (幅優先探索による単一始点最短経路, 次元拡張に対応)
 *
 * @param dist:
 *      start からの距離を格納する配列。
 *      要素数は頂点数以上でなければならない。-1や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) => void) => void
 *      第一引数にVertex, 第二引数に関数をとる関数。
 *      この関数が第一引数の頂点fromから次の頂点の遷移先を列挙し、第二引数に渡すことで bfs() に遷移処理を委譲する。
 */
template <class DistArray, class Vertex, class NextVertexEnumerator>
DistArray bfs(DistArray&& dist, Vertex start, NextVertexEnumerator enumerateNextVertex) {
    using arumakan::at;
    assert(!dist.empty());
    assert(at(dist, start) == -1 || at(dist, start) >= INF);

    std::queue<Vertex> que({start});
    const auto yetReachedMarker = at(dist, start);
    at(dist, start) = 0;
    while (!que.empty()) {
        const Vertex v = std::move(que.front());
        que.pop();
        const auto curDist = at(dist, v);
        enumerateNextVertex(v, [&](Vertex nxt) {
            if (at(dist, nxt) == yetReachedMarker) {
                at(dist, nxt) = curDist + 1;
                que.push(nxt);
            }
        });
    }
    return dist;
}

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

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

/**
 * @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/int-infinity.hpp"
#include <cstdint>

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

/**
 * @brief bfs() (幅優先探索による単一始点最短経路, 次元拡張に対応)
 *
 * @param dist:
 *      start からの距離を格納する配列。
 *      要素数は頂点数以上でなければならない。-1や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) => void) => void
 *      第一引数にVertex, 第二引数に関数をとる関数。
 *      この関数が第一引数の頂点fromから次の頂点の遷移先を列挙し、第二引数に渡すことで bfs() に遷移処理を委譲する。
 */
template <class DistArray, class Vertex, class NextVertexEnumerator>
DistArray bfs(DistArray&& dist, Vertex start, NextVertexEnumerator enumerateNextVertex) {
    using arumakan::at;
    assert(!dist.empty());
    assert(at(dist, start) == -1 || at(dist, start) >= INF);

    std::queue<Vertex> que({start});
    const auto yetReachedMarker = at(dist, start);
    at(dist, start) = 0;
    while (!que.empty()) {
        const Vertex v = std::move(que.front());
        que.pop();
        const auto curDist = at(dist, v);
        enumerateNextVertex(v, [&](Vertex nxt) {
            if (at(dist, nxt) == yetReachedMarker) {
                at(dist, nxt) = curDist + 1;
                que.push(nxt);
            }
        });
    }
    return dist;
}