C++の練習を兼ねて, AtCoder Beginner Contest 068 の 問題C（Cat Snuke and a Voyage）を解いてみた.
■感想.
島1 から 島N に行くために経由する島 を 如何にして, 探索するか, という点が, 面白いと思った.
本家のサイトAtCoder Regular Contest 079 Editorialをご覧下さい.
■C++版プログラム.
|
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 |
#include <iostream> #include <map> using namespace std; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) typedef long long LL; int main() { // 1. 入力情報取得. LL N, M; cin >> N >> M; // 2. 島1 -> 島x -> 島N となる 島x は, 存在するか？ // 島1 は, ai から探索し, 見つかったら, 対応する bi を すべて map1 に 保存. // 島N は, bi から探索し, 見つかったら, 対応する ai を すべて mapN に 保存. // -> このとき, map1 と mapN に, 共通する値が存在する場合, 島x が見つかったと判定できる. map<LL, LL> map1, mapN; FOR(i, 0, M) { LL ai, bi; cin >> ai >> bi; if(ai == 1LL) map1[bi]++; if(bi == N) mapN[ai]++; } // 3. 判定. // map1, mapN に共通の値が存在しているかチェック. bool ok = false; for(auto i = map1.begin(); i != map1.end(); ++i){ if(mapN.count(i->first) > 0) { ok = true; break; } } // 4. 出力 ～ 後処理. cout << (ok ? "POSSIBLE" : "IMPOSSIBLE") << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 068