ALDS1_12_C: Single Source Shortest Path II (続き2)

解説を読む

まず、隣接行列じゃなくて隣接リストを使う
Iで隣接行列を使ったのは、IIで隣接リストを使うから、ってだけだったかも

さて本筋

なるほど、順次追加していくんじゃなくて
二分ヒープにまず全部入れてしまって
取り出して更新してヒープを再構築を繰り返すのか

と思ったら優先度付きキューの方が直感的で簡単だって
どんな感じ？

だいたいは自分のコードと似てるけど
BLACKだったら最初からキューに入れない＆最小値のときだけ更新、ってなってる
確かにそのほうがよさそうだ

と思ってサンプルコード見ながら書き直したんだけどうまく動かない

def shortest_path(nodes):
    h = []

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

    while len(h) > 0:
        min_node, min_dist = heappop(h)

        nodes[min_node].color = Node.BLACK
        if nodes[min_node].dist < min_dist:
            continue

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

この2行がなければちゃんとした答えが出るんだけど

            if nodes[adj].color == Node.BLACK:
               continue

おかしい