[Codeforces] Round #536 D. Lunar New Year and a Wander

Lunar New Year and a Wander

https://codeforces.com/contest/1106/problem/D

考え方

題意

\( n \) 個のノードと \( m \) 本の無向辺からなる連結グラフが与えられます。初めて訪れたノードを記録したとき、辞書式順列で最小となるようなパターンを答えます。

方針

最初に訪れるノードは自由に選べるので、ノード \( 1 \) を選びます。

ノードを訪れるごとにそのノードの隣接ノードを優先度付きキューにいれることを考えます。このキューにあるノードは現在の状態から訪れることができるノードなので、その中で一番小さいノードを選びます。そして、そのノードの隣接するノードをキューにいれることを繰り返します。

また、キューに入れたノードを管理することで、無駄な計算を行わないようにします。

コード

感想

優先度付きキューを使うところがポイントだと思いました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする