ALDS1_12_C: Single Source Shortest Path II (続き)

続き

そもそもキューに何を入れるんだってとこもある
キーはdistだけど、distだけ覚えても仕方なくてNodeの情報と
結び付けられないといけないんだけど、数じゃなくても入るのかな

heapqのドキュメントを見てみる
タプルを入れればタプルの第一要素から比較してくれるっぽい
(node.dist, node)という形のタプルで入れてみる
nodeの中にもdistがあるので重複してて気持ち悪いけど
が、これだとnode.distどうしが等しいとにnodeを比較しにいってエラー
Nodeのインスタンスには"<"が定義されてないよって

てことは"<"を定義してやればいいのか？
試してみるとどうやらいけそう
Nodeどうしを直接"<"で比較できればタプルにする必要もなくてうれしい

そっちはそれでいいとして更新
キューに入れちゃったけどあとでもっといい値が見つかったらどうするか
知らんぷりして新しい値を入れてみるかまずは
小さい方の値が大事なんだし、小さい方が見つかればcolorがBLACKになるので
その後はキューから出てきても無視される
案外うまくいくのでは

from heapq import heappop, heappush

class Node:
    def __lt__(self, other):
        return self.dist < other.dist

def shortest_path(nodes):
    h = []

    nodes[0].dist = 0
    nodes[0].color = Node.GRAY
    heappush(h, nodes[0])

    while True:
        while len(h) > 0:
            min_node = heappop(h)
            if min_node.color != Node.BLACK:
                break
        else:
            break

        min_node.color = Node.BLACK

        for adj, c in min_node.adjs:
            if min_node.dist + c < adj.dist:
                adj.dist = min_node.dist + c
                adj.color = Node.GRAY
                heappush(h, adj)

なんかうまくいった
うまくいかれても困る的な
n=10000で0.051s