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

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
- 出版社/メーカー: マイナビ
- 発売日: 2015/01/30
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (7件) を見る
端的にいうと、「最短経路長が未確定のノードの中で『現時点で最も経路長が短いノード』だけは確定できる」ということです。
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)
本日のおまけ
読んだ本の紹介。
イーロン・マスクほどエネルギッシュな人もいないと思った。この人は行動力、ストイックさ、信念が全部一級品。

- 作者: アシュリー・バンス,斎藤栄一郎
- 出版社/メーカー: 講談社
- 発売日: 2015/09/16
- メディア: ペーパーバック
- この商品を含むブログ (5件) を見る

- 作者: 竹内一正
- 出版社/メーカー: ダイヤモンド社
- 発売日: 2018/01/25
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る