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の方はファイルがダウンロードできたっけ?