#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;
}
test/AOJ/GRL_1_A-Single-Source-Shortest-Path.test.cpp