ゆる〜くpythonの練習「ダイクストラ法編」

今回はダイクストラのアルゴリズムです。
問題はこちら(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_C)です。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

ダイクストラのアルゴリズムはヨビノリ先生のめっちゃわかりやすい動画があるので、こちらをご覧ください。

端的にいうと、「最短経路長が未確定のノードの中で『現時点で最も経路長が短いノード』だけは確定できる」ということです。

from heapq import heappush,heappop,heapify

n = int(input())
G = [[] for _ in range(n)]
info = []

for i in range(n):
    info =  list(map(int,(input().split())))[2:]
    for j in range(int((len(info))/2)):
        G[i].append((info[2*j],info[2*j+1]))

color = ["white" for _ in range(n)]
dist = [(1<<21) for _ in range(n)]
que = []

def dijkstra():
    dist[0] = 0
    que.append((0,0)) #(dist,node)
    while que:
        now = heappop(que)
        u = now[1]
        if dist[u] < now[0]:
            continue
        color[u] = "black"
        for j in range(len(G[u])):
            if dist[u] + G[u][j][1] < dist[G[u][j][0]]:
                heappush(que,(dist[u] + G[u][j][1],G[u][j][0]))
                dist[G[u][j][0]] = dist[u] + G[u][j][1]

dijkstra()

for i,dist in enumerate(dist):
    print(i,dist)

本日のおまけ
読んだ本の紹介。
イーロン・マスクほどエネルギッシュな人もいないと思った。この人は行動力、ストイックさ、信念が全部一級品。

イーロン・マスク 未来を創る男

イーロン・マスク 世界をつくり変える男