drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder400点 ABC-D グラフ 最短路問題 構築 BFS 復元 最適化の考察：最適解に必ず含まれる要素を列挙する Yes/No判定問題 緑色diff DFS木やBFS木を考察する 【問題集】DFS・BFSのステップアップ 典型要素を詰め合わせた教育的問題 そのまま覚えたい典型問題 NoviSteps2Q BFS 木とか、BFS による経路復元とか、その辺りの理解を問いかける教育的問題だった！！！ 問題へのリンク 問題概要 頂点、 辺の無向グラフが与えられる。頂点 1 以外のすべての頂点に対し「みちしるべとなる頂点」を、以下の条件を満たすように設定することが可能かどうかを判定し、可能ならば一例を示せ。 頂点 1 以外の任意の頂点 v に対し、その頂点から「みちしるべとなる頂点」を順に進むと、理論最短で頂点 1 にたどり着く 制約 グラフは連結 考えたこと 問いかけがトリッキーだけど、グラフが連結である限り、かならず Yes になる！この問題は、シンプルに BFS 木というものについての理解があれ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F06%2F20%2F174100" title="AtCoder ABC 168 D - .. (Double Dots) (2Q, 緑色, 400 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/d/drken1215/20200620/20200620173110.png Hatena Blog https://hatena.blog 2020-06-20 17:41:00 rich https://drken1215.hatenablog.com/entry/2020/06/20/174100 1.0 100%