競技プログラミング総合スレ 66 (478ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
172(1): (ﾜｯﾁｮｲ 8255-dXWb) 2023/04/09(日)18:19 ID:l3qXUMY00(5/7) AAS
ヒープにプッシュする前に、そのノードがマークされていないことをチェックしています。
ですので、ヒープ内には、マークされていないノードしか入れないと思うのですが。
174: (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/09(日)18:28 ID:fcL4nlHr0(2/3) AAS
>>172
確かに、ヒープにプッシュする前にそのノードがマークされていないことをチェックしています。
ただし、ヒープにプッシュされた後で、そのノードが他の辺を経由してマークされる可能性があります。
そのため、ヒープから辺を取り出す前にもう一度マークされているかどうかをチェックする必要があります。
先程のグラフで考えてみましょう。キューがこの様になったところから解説します。
(1, 3), (1, 1), (1, 3)
ここで、最初に(1, 3)をキューから取り出し、頂点3をマークします。この時点で、キューには以下のような状態が残っています。
省5
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.714s*