Link Search Menu Expand Document
あるまかんライブラリ

:heavy_check_mark: test/AOJ/GRL_1_A-Single-Source-Shortest-Path.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp"

#include <iostream>
#include <vector>

#include "../../Graph/graph-template.hpp"
#include "../../Graph/Shortest-Path/dijkstra.hpp"
#include "../../Util/IO/read-directed-graph.hpp"

#include "../../Util/int-alias.hpp"
#include "../../Util/int-infinity.hpp"
#include "../../Util/IO/println.hpp"

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    int V, E, r;
    std::cin >> V >> E >> r;

    auto G = readDirectedGraph<int>(V, E, 0);

    std::vector<i64> dist(V, LINF);
    dijkstra(dist, r, [&](int v, auto push) {
        for (Edge e : G[v]) {
            push(e.to, e.weight);
        }
    });

    for (const auto d : dist) {
        if (d >= LINF) {
            println("INF");
        } else {
            println(d);
        }
    }

    return 0;
}
#line 1 "test/AOJ/GRL_1_A-Single-Source-Shortest-Path.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp"

#include <iostream>
#include <vector>

#line 2 "Graph/graph-template.hpp"
#include <cstdint>
#line 5 "Graph/graph-template.hpp"

/**
 * @brief graph-template (Edge, Graph, MatrixGraph)
 */
//! グラフの辺 (重み付き)
template <class T>
struct Edge {
    int from, to;
    T weight;
    int id;

    Edge() = default;

    constexpr explicit Edge(int to_, const T& weight_)
        : Edge(-1, to_, weight_, -1) {}

    constexpr Edge(int from_, int to_, const T& weight_, int id_ = -1)
        : from(from_)
        , to(to_)
        , weight(weight_)
        , id(id_) {}

    constexpr const Edge rev() const { return Edge(to, from, weight, id); }

    template <class Int, std::enable_if_t<std::is_integral<Int>::value, std::nullptr_t> = nullptr>
    constexpr operator Int() const {
        return static_cast<Int>(to);
    }

    friend std::istream& operator>>(std::istream& is, Edge& e) { return is >> e.from >> e.to >> e.weight; }
};

//! グラフの辺 (重みなし)
template <>
struct Edge<void> {
    int from, to;
    int id;

    Edge() = default;

    constexpr explicit Edge(int to_)
        : Edge(-1, to_, -1) {}

    constexpr Edge(int from_, int to_, int id_ = -1)
        : from(from_)
        , to(to_)
        , id(id_) {}

    constexpr const Edge rev() const { return Edge(to, from, id); }

    template <class Int, std::enable_if_t<std::is_integral<Int>::value, std::nullptr_t> = nullptr>
    constexpr operator Int() const {
        return static_cast<Int>(to);
    }

    friend std::istream& operator>>(std::istream& is, Edge& e) { return is >> e.from >> e.to; }
};

template <class T>
using Graph = std::vector<std::vector<Edge<T>>>;
#line 2 "Graph/Shortest-Path/dijkstra.hpp"
#include <cassert>
#include <functional>
#include <queue>
#include <type_traits>
#include <utility>
#line 8 "Graph/Shortest-Path/dijkstra.hpp"

#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 3 "Util/int-infinity.hpp"

/**
 * @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;
}

#line 4 "Util/IO/read-directed-graph.hpp"

#line 6 "Util/IO/read-directed-graph.hpp"

/**
 * @brief readDirectedGraph() (有向グラフの入力)
 */
template <class T>
Graph<T> readDirectedGraph(size_t V, size_t E, int padding = -1, std::istream& is = std::cin) {
    Graph<T> G(V);
    for (size_t i = 0; i < E; ++i) {
        Edge<T> e;
        is >> e;
        e.from += padding, e.to += padding;
        e.id = static_cast<int>(i);
        G[e.from].emplace_back(e);
    }
    return G;
}

#line 9 "test/AOJ/GRL_1_A-Single-Source-Shortest-Path.test.cpp"

#line 3 "Util/int-alias.hpp"

/**
 * @brief int-alias (整数型のエイリアス)
 */
using i64 = int64_t;
using u64 = uint64_t;
#line 4 "Util/IO/println.hpp"

/**
 * @brief println() (可変個の値を空白区切りで出力して改行する)
 */
inline void println() {
    std::cout << '\n';
}
template <class Head, class... Tail>
inline void println(Head&& head, Tail&&... tail) {
    std::cout << head << &" "[!sizeof...(tail)];
    println(std::forward<Tail>(tail)...);
}
#line 13 "test/AOJ/GRL_1_A-Single-Source-Shortest-Path.test.cpp"

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    int V, E, r;
    std::cin >> V >> E >> r;

    auto G = readDirectedGraph<int>(V, E, 0);

    std::vector<i64> dist(V, LINF);
    dijkstra(dist, r, [&](int v, auto push) {
        for (Edge e : G[v]) {
            push(e.to, e.weight);
        }
    });

    for (const auto d : dist) {
        if (d >= LINF) {
            println("INF");
        } else {
            println(d);
        }
    }

    return 0;
}
Back to top page