test/bfs.test.cpp
Depends on
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