C++の練習を兼ねて, AtCoder Beginner Contest 218 の 問題F (Blocked Roads) を解いてみた.
■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 218 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
// 解き直し. // https://atcoder.jp/contests/abc218/editorial/2606 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vs = vector<set<int>>; using vp = vector<P>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back #define a first #define b second int info[404][404]; // 最短経路を構成する辺情報. int memo[404][404]; // 最短経路上の辺情報. int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); vs OG(N), RG(N); vp edges; rep(i, M){ int s, t; scanf("%d %d", &s, &t); s--, t--; OG[s].insert(t); // 有向グラフ. RG[t].insert(s); // 有向グラフ(逆向き). edges.pb({s, t}); // 有向辺. } // 2. bfs. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](vs &G, int s, int* d){ // 空のキュー. queue<int> q; // 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // キューから取り出す. int u = q.front(); q.pop(); // 取り出した要素を処理. for(auto &e : G[u]){ // 訪問済であれば, 処理をスキップ. if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e); } } return; }; // 3. 最短距離(グラフの有向辺が, 全てそろっている場合). int d[N]; rep(i, N) d[i] = 0; bfs(OG, 0, d); // 4. 最短経路を取得. // -> 到達可能な場合に, 最短経路を取得(ゴールから逆算). auto f = [&](vs &G, int s, int* d){ // 空のキュー. queue<int> q; // 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // キューから取り出す. int u = q.front(); q.pop(); // 取り出した要素を処理. for(auto &e : G[u]){ // 距離 が 1 小さい場合に, 最短経路として保存. if(d[e] == d[u] - 1){ info[e][u]++; q.push(e); break; } } } return; }; int D = d[N - 1]; if(D) f(RG, N - 1, d); // 5. クエリ回答. for(auto &e : edges){ // 辺情報. int u = e.a; // 始点. int v = e.b; // 終点. // 到達不可能な場合. if(!D) puts("-1"); // 到達可能な場合. if(D){ // 辺(u, v) が, 最短経路上に無い場合. if(!info[u][v]) printf("%d\n", D); // 辺(u, v) が, 最短経路上に有る場合. if(info[u][v]){ // 探索済みの場合. if(memo[u][v] != 0) printf("%d\n", memo[u][v]); // 探索済みでない場合. if(memo[u][v] == 0){ // グラフから, 辺を削除. OG[u].erase(v); // bfs. int duv[N]; rep(i, N) duv[i] = 0; bfs(OG, 0, duv); // 探索結果を保存. memo[u][v] = duv[N - 1] ? duv[N - 1] : -1; // グラフに, 辺を戻す. OG[u].insert(v); // 出力. printf("%d\n", memo[u][v]); } } } } return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
[入力例] 3 3 1 2 1 3 2 3 [出力例] 1 2 1 ※AtCoderテストケースより [入力例] 4 4 1 2 2 3 2 4 3 4 [出力例] -1 2 3 2 ※AtCoderテストケースより [入力例] 5 10 1 2 1 4 1 5 2 1 2 3 3 1 3 2 3 5 4 2 4 3 [出力例] 1 1 3 1 1 1 1 1 1 1 ※AtCoderテストケースより [入力例] 4 1 1 2 [出力例] -1 ※AtCoderテストケースより [入力例] 5 3 1 2 3 4 3 5 [出力例] -1 -1 -1 [入力例] 7 9 1 3 3 4 1 4 4 2 7 4 2 5 5 6 6 7 2 7 [出力例] 3 3 4 -1 3 3 3 3 5 [入力例] 18 24 1 2 1 3 3 6 2 5 6 2 6 7 7 4 4 5 5 8 8 4 8 9 8 10 9 10 10 11 10 17 10 18 10 12 12 15 12 13 12 14 13 14 14 16 13 18 18 14 [出力例] 7 5 5 8 5 5 5 5 -1 5 5 6 5 5 5 7 5 5 5 5 5 5 5 5 |
■参照サイト
AtCoder Beginner Contest 218