GRL_2_A: Minimum Spanning Tree (続き2)

前にもそういうのあったっけな？

ALDS1_12_Cだな
ダイクストラのアルゴリズムと優先度付きキューを組み合わせたやつ
見比べてみるにほぼそっくりなんだけど

    if (d[u] < f.first * (-1)) continue;

に相当することは書けるだろうか
ダイクストラのアルゴリズムでは、キューから取り出した頂点のコストが
すでに計算済みのコストよりも大きければ意味がなかった
プリムのアルゴリズムだとそこまでのコスト計算してないし

    while heap != []:
        u = heapq.heappop(heap)
        if u.color == BLACK:
            continue
        u.color = BLACK

こうやって、訪問済みだったら処理しないってくらいかな？

同じNodeがheapに2回以上突っ込まれることがありそうな気がして気になる
heapに入れたNodeの値を変えてしまってるわけでもあるし

2回入れちゃってたときに2回目は処理しないという効果はあるかな
入れてから値を変えてるっていう気持ち悪さは残るけど
前もこんなこと書いてた

小さい方の値が大事なんだし、小さい方が見つかればcolorがBLACKになるので
その後はキューから出てきても無視される
案外うまくいくのでは

でも同じところでWA
今度は通用しなかった？
どこが間違ってる？

古いUIの方はファイルがダウンロードできたっけ？

こっちからいけば入力ファイルがダウンロードできる
うん、確かに間違ってる
でもデータが大きすぎてどこで間違ってるのかわからない

困った

kb84tkhrのブログ