#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C" #include <iostream> #include <vector> #include "../../Graph/graph-template.hpp" #include "../../Graph/Shortest-Path/bfs.hpp" #include "../../Util/IO/var-declaration-with-input.hpp" #include "../../Util/IO/println.hpp" int main() { var(int, N); Graph<void> G(N); for (int i = 0; i < N; ++i) { var(int, u, k); --u; while (k--) { var(int, v); --v; G[u].emplace_back(v); } } std::vector<int> dist(N, -1); bfs(dist, 0, [&](int v, auto push) { for (const int to : G[v]) push(to); }); for (int i = 0; i < N; ++i) { println(i + 1, dist[i]); } return 0; }
#line 1 "test/AOJ/ALDS1_11_C-Breadth-First-Search.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C" #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/bfs.hpp" #include <cassert> #include <functional> #include <queue> #include <utility> #line 7 "Graph/Shortest-Path/bfs.hpp" #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 3 "Util/int-infinity.hpp" /** * @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; } #line 8 "test/AOJ/ALDS1_11_C-Breadth-First-Search.test.cpp" #line 3 "Util/IO/var-declaration-with-input.hpp" /** * @brief 複数変数宣言をして同時に入力もするやつ */ template <class T> std::istream& operator,(std::istream& is, T& rhs) { return is >> rhs; } #define var(type, ...) \ type __VA_ARGS__; \ std::cin >> __VA_ARGS__ #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 11 "test/AOJ/ALDS1_11_C-Breadth-First-Search.test.cpp" int main() { var(int, N); Graph<void> G(N); for (int i = 0; i < N; ++i) { var(int, u, k); --u; while (k--) { var(int, v); --v; G[u].emplace_back(v); } } std::vector<int> dist(N, -1); bfs(dist, 0, [&](int v, auto push) { for (const int to : G[v]) push(to); }); for (int i = 0; i < N; ++i) { println(i + 1, dist[i]); } return 0; }