ALDS1_12_B: Single Source Shortest Path I (続き)

解説
今度は隣接行列にしてるのか
気が合いませんね（そういう問題？

ダイクストラ法
たしかレナの本にも出てたな（名前しか記憶がない

グラフG=(V, E)、始点をs、最短経路木に含まれる頂点の集合をS、
sから各頂点iまでのコストをd[i]、iの親をp[i]とする

S={}、d[s]=0、s以外の頂点iについてd[i]=∞に初期化する
S=Vになるまで以下を繰り返す
V-Sからd[u]が最小であるuを選択する
uをSに追加する
uに隣接しV-Sの属する頂点vについてd[v]とp[v]を更新する

という作戦とサンプルコードを参考にしつつ修正

def shortest_path(n, adj_list):
    color = [WHITE] * n
    dist = [maxsize] * n

    dist[0] = 0
    color[0] = GRAY

    while True:
        minv = maxsize
        u = -1
        for i in range(n):
            if minv > dist[i] and color[i] != BLACK:
                u = i
                minv = dist[i]

        if u == -1:
            break
        color[u] = BLACK

        for v, c in adj_list[u]:
            if dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                color[v] = GRAY

    return dist

テスト#6が00.02s
20倍速くなった（なお有効数字

全体的な流れはMinimun Spanning Treeと似てるんだな
境界上で最短となる辺を探すから無駄が少ないと
IIでは速い方法を考えるのか？

思い立ってインデックスでループを回すのをやめてみた

class Node:
    WHITE = 0
    GRAY = 1
    BLACK = 2

    def __init__(self):
        self.adjs = []
        self.color = Node.WHITE
        self.dist = maxsize

def read_adj():
    n = int(input())
    nodes = [Node() for _ in range(n)]

    for i in range(n):
        u, _, *rest = [int(x) for x in input().split()]
        for i in range(0, len(rest) - 1, 2):
            nodes[u].adjs.append((nodes[rest[i]], rest[i+1]))

    return nodes

def shortest_path(nodes):
    nodes[0].dist = 0
    nodes[0].color = Node.GRAY

    while True:
        min_node = min(
            [n for n in nodes if n.color != Node.BLACK],
            default=None, key=lambda n: n.dist)

        if min_node is None:
            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