競技プログラミング用 知識集積所
ABC417E - A Path in A Dictionary
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
辞書順最小ということは、とにかく優先的に前をなるべく小さくする貪欲法（未作成）で考える。
最初はスタート地点で固定として、次の1つは隣接リスト（未作成）から番号がもっとも若いものを選べばよい。
とはいえ、選んだものが重複したり、そこからゴール不可能だったりするのはさすがに困る。
とはいえ、選んだものが重複したり、そこからゴール不可能だったりするのはさすがに困る。
そこで、ある頂点を通ると決めたときに、その頂点へ向かう辺をグラフから全て削除してしまうことにする。
これは、隣接リスト（未作成）をvector<set（未作成）>で作っておくことで簡単に可能。
（若い番号を探したいという意味でも都合がいい）
すると、ゴールから幅優先探索をすることで、そこからちゃんとゴール可能な頂点かどうかが判別でき、「ゴール可能な中で最も若い番号」を求められる。
これは、隣接リスト（未作成）をvector<set（未作成）>で作っておくことで簡単に可能。
（若い番号を探したいという意味でも都合がいい）
すると、ゴールから幅優先探索をすることで、そこからちゃんとゴール可能な頂点かどうかが判別でき、「ゴール可能な中で最も若い番号」を求められる。
1回の幅優先探索がO(N+M)、それが最大でO(N)回行われるとして、計算回数的には（わりとギリギリだが）間に合う。
