test/bfs.test.cpp

• View this file on GitHub
• Last update: 2022-08-28 17:14:39+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=ja

Depends on

• graph/bfs.cpp

Code

#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=ja"
#include "../graph/bfs.cpp"

int main() {
    int n;
    cin >> n;
    vector<vector<int>> G(n);
    for (int i = 0; i < n; i++) {
        int u, k;
        cin >> u >> k;
        --u;
        for (int j = 0; j < k; j++) {
            int v;
            cin >> v;
            --v;
            G[u].push_back(v);
        }
    }

    Bfs<int> bfs(n, G);
    bfs.shortest_path(0);
    for (int i = 0; i < n; i++) {
        cout << i + 1 << ' ' << bfs.dist[i] << '\n';
    }

    return 0;
}

#line 1 "test/bfs.test.cpp"
#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=ja"
#line 3 "graph/bfs.cpp"
using namespace std;

// Bfs
// nは頂点数, Gはグラフを隣接リスト形式で持ったもの
template <typename T>
struct Bfs {
    int n;
    vector<vector<int>> G;
    vector<int> dist, prev_v;

    Bfs(int n, vector<vector<int>> G) : n(n), G(G) {
        dist.assign(n, -1);
        prev_v.assign(n, -1);
    }

    // shortest_path
    // 頂点sから他の任意の頂点までの最短距離を求める.
    // 制約: 0 <= s < n
    void shortest_path(int s) {
        fill(dist.begin(), dist.end(), -1);
        dist[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto &u : G[v]) {
                if (dist[u] >= 0) continue;
                dist[u]   = dist[v] + 1;
                prev_v[u] = v;
                q.push(u);
            }
        }
    }

    // restore_path
    // 頂点sからtまでの最短経路を求める。
    // 最短経路が存在する場合, 返り値は先頭にs,tを含む. 存在しないとき空を返す.
    // 制約: sは以前にshortest_path(s)が呼ばれている. 0 <= t < n
    // 未Verify
    vector<int> restore_path(int s, int t) {
        if (dist[s] != 0) {
            cerr << "error when restore_path() is called.";
            exit(1);
        }
        if (dist[t] < 0) return {};

        vector<int> ret;
        int now_v = t;
        ret.push_back(now_v);
        while (now_v != s) {
            now_v = prev_v[now_v];
            ret.push_back(now_v);
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};
#line 6 "test/bfs.test.cpp"

int main() {
    int n;
    cin >> n;
    vector<vector<int>> G(n);
    for (int i = 0; i < n; i++) {
        int u, k;
        cin >> u >> k;
        --u;
        for (int j = 0; j < k; j++) {
            int v;
            cin >> v;
            --v;
            G[u].push_back(v);
        }
    }

    Bfs<int> bfs(n, G);
    bfs.shortest_path(0);
    for (int i = 0; i < n; i++) {
        cout << i + 1 << ' ' << bfs.dist[i] << '\n';
    }

    return 0;
}

Back to top page