kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

GRL_2_A: Minimum Spanning Tree (続き)

プリムのアルゴリズムは、二分ヒープ(優先度付きキュー)を使って頂点を決定するようにすれば、高速化を行うことができます。

heapq使うよ!
こう・・・かな?

import heapq

class Node():

    def __lt__(self, other):
        return self.d < other.d

def min_sp_tree(G):
    heap = []
    G[0].d = 0
    heapq.heappush(heap, G[0])

    while heap != []:
        u = heapq.heappop(heap)
        u.color = BLACK
        for a, w in u.adj:
            if a.color != BLACK and a.d > w:
                a.d = w
                a.p = u
                a.color = GRAY
                heapq.heappush(heap, a)

    return sum([v.d for v in G if v.p is not None])

同じNodeがheapに2回以上突っ込まれることがありそうな気がして気になる
heapに入れたNodeの値を変えてしまってるわけでもあるし
前にもそういうのあったっけな?
短くなったのは気分いいんだけれども


やってみるとCase #4は超えたけど#7でWA
Case #7のデータは大きすぎてブラウザに表示されないのが困る
表示できる大きさのCase #13〜#16では間違えないようだし

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