競技プログラミング総合スレ 66 (478ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
171(2): (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/09(日)18:19 ID:fcL4nlHr0(1/3) AAS
この部分は、既にマークされた頂点に対応する辺をスキップするために必要です。
確かに、キューには基本的にmarkedの値がFalseのノードしか入らないように見えますが、
実際には同じノードに対して複数の辺がキューに入ることがあります。
例えば、次のようなグラフを考えてみましょう。
1 -- 2
| /
| /
省16
173: (ﾜｯﾁｮｲ 8255-dXWb) 2023/04/09(日)18:25 ID:l3qXUMY00(6/7) AAS
>>171
あまり参考にならないだろうと思って読んでいたらなぜか理由が分かりました。
マークされていない状態で、同じノードが複数個ヒープに入ることがあるわけですね。
175(1): (ﾜｯﾁｮｲ 8255-dXWb) 2023/04/09(日)18:28 ID:l3qXUMY00(7/7) AAS
>>171
この場合でいうとノード3が2回ヒープに入るわけですね。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.018s