AOJ pythonでダイクストラ法の勉強

・問題:
onlinejudge.u-aizu.ac.jp

ダイクストラ法の詳しい解説:グラフ理論⑤(ダイクストラのアルゴリズム) - YouTube

・やること:ダイクストラ法のプログラムの勉強のため上のAOJの問題を解く。

・プログラムの説明:はじめに辺がないときの処理をする。またG[s]にsからいける点tとその重さdを入れる。rから始めるのでdequeにrを入れてdist[r]=0(重さが0からスタート)で重さの最小値を更新していく。

・実装例:

from collections import deque
v,e,r=map(int,input().split())  #頂点数と辺、始点

#辺がないとき、始点の番号以外はINF。
if e==0:
  for i in range(v):
    if i==r:
      print(0)
    else:
      print("INF")
  exit()

G=[[] for _ in range(v)]
for i in range(e):
  s,t,d=map(int,input().split())
  G[s].append((t,d))  #sからいけるのがt。dはその重さ。

#print(G) #入力は一個目のテストケースで[[(1, 1), (2, 4)], [(2, 2), (3, 5)], [(3, 1)], [], []]
#for i in range(e):
#  for j,k in G[i]:
#    print(j,k)    #1 1,2 4,2 2,3 5,3 1

dist=[10**18 for _ in range(v)]   #distは辺の重さの最小の合計
dist[r]=0

que=deque()
que.append(r)

while len(que)!=0:
  pl=que.popleft()
  
  #plから行ける点がp、その重さがl
  for p,l in G[pl]:   #上のコメントアウト参照
    d=dist[pl]+l   

    #distが更新できるなら
    if d<dist[p]:
      dist[p]=d
      que.append(p)
    
#出力
for i in range(v):    
  if dist[i]==10**18:
    print("INF")
  else:
    print(dist[i])