test/simple-bfs2.test.cpp

• View this file on GitHub
• Last update: 2022-12-06 05:52:19+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc148/submissions/37049186

Depends on

• Read-Graph (グラフ入力) (src/graph/Read-Graph.hpp)
• bfs (simple ver) (src/graph/simple/bfs.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../src/graph/simple/bfs.hpp"
#include "../src/graph/Read-Graph.hpp"

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // int n, u, v; std::cin >> n >> u >> v;
    // u--; v--;
    // auto G = zawa::read_tree(n);
    // auto distT = zawa::bfs(G, u);
    // auto distA = zawa::bfs(G, v);
    // std::vector oks(0, 0);
    // for (int i = 0 ; i < n ; i++) {
    //     if (distT[i] < distA[i]) {
    //         oks.push_back(distA[i]);
    //     }
    // }
    // std::cout << *std::max_element(oks.begin(), oks.end()) - 1 << std::endl;

    std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 148 - F Playing Tag on Tree
 * https://atcoder.jp/contests/abc148/submissions/37049186
 */

#line 1 "test/simple-bfs2.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "src/graph/simple/bfs.hpp"

#include <vector>
#include <queue>

namespace zawa {

std::vector<int> bfs(const std::vector<std::vector<int>>& G, int s, int inf = 2e9) {
    std::vector<int> res(G.size(), inf);
    res[s] = 0;
    std::queue<int> que({ s });
    while (que.size()) {
        int v = que.front();
        que.pop();
        for (auto x : G[v]) {
            if (res[x] > res[v] + 1) {
                res[x] = res[v] + 1;
                que.push(x);
            }
        }
    }
    return res;
}

} // namespace zawa
#line 2 "src/graph/Read-Graph.hpp"

#line 4 "src/graph/Read-Graph.hpp"
#include <iostream>

namespace zawa {

std::vector<std::vector<int>> read_graph(int n, int m, bool undirect = true, bool minus = true) {
    std::vector<std::vector<int>> res(n, std::vector(0, 0));
    for (int _ = 0 ; _ < m ; _++) {
        int u, v;
        std::cin >> u >> v;
        res[u - minus].emplace_back(v - minus);
        if (undirect) {
            res[v - minus].emplace_back(u - minus);
        }
    }
    return res;
}

std::vector<std::vector<int>> read_tree(int n, bool undirect = true, bool minus = true) {
    return read_graph(n, n - 1, undirect, minus);
}

}
#line 5 "test/simple-bfs2.test.cpp"

#line 8 "test/simple-bfs2.test.cpp"
#include <algorithm>

int main() {
    // int n, u, v; std::cin >> n >> u >> v;
    // u--; v--;
    // auto G = zawa::read_tree(n);
    // auto distT = zawa::bfs(G, u);
    // auto distA = zawa::bfs(G, v);
    // std::vector oks(0, 0);
    // for (int i = 0 ; i < n ; i++) {
    //     if (distT[i] < distA[i]) {
    //         oks.push_back(distA[i]);
    //     }
    // }
    // std::cout << *std::max_element(oks.begin(), oks.end()) - 1 << std::endl;

    std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Beginner Contest 148 - F Playing Tag on Tree
 * https://atcoder.jp/contests/abc148/submissions/37049186
 */

Back to top page