#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; }