競技プログラミング総合スレ 66 (478ﾚｽ)
競技プログラミング総合スレ 66 http://mevius.5ch.net/test/read.cgi/tech/1679465982/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
175: デフォルトの名無しさん (ﾜｯﾁｮｲ 8255-dXWb) [] 2023/04/09(日) 18:28:12.80 ID:l3qXUMY00 >>171 この場合でいうとノード3が2回ヒープに入るわけですね。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/175
176: デフォルトの名無しさん (ﾜｯﾁｮｲ 412d-dXWb) [sage] 2023/04/09(日) 18:31:35.09 ID:fcL4nlHr0 >>175 はい、その通りです。 最初にノード1からノード3への辺がヒープに追加され、次にノード2からノード3への辺がヒープに追加されます。 (1, 3) <-- 1から3への辺 (1, 1) (1, 3) <-- 2から3への辺 このように、同じノードが複数回ヒープに入ることがあります。プリムのアルゴリズムでは、 すでにマークされた頂点に対応する辺を無視する必要があります。 そのため、ヒープから辺を取り出す前にマークされているかどうかをチェックする必要があるのです。 http://mevius.5ch.net/test/read.cgi/tech/1679465982/176
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.429s*