【Python】ダイグストラ法(自分自身への最短経路もOK)【AtCoder】

ABC191
E - Come Back Quickly
でダイグストラが出てきたので今後のためにも自作ライブラリ作った！

※ABC191EでAC確認済ですが、万が一バグがあれば教えてください！

---

###ちなみに
Pythonの標準ライブラリ
scipy.sparse.csgraphの関数shortest_path()
は、以下の2点の場合、競プロでは使えない。

• N>=10**4 の場合
  • 計算量がO[N(N*k + N*log(N))]>=O[N**2]なため。隣接行列を作る過程で、O[N**2]になる。
• 自分自身への最短経路を算出できない
  • 自分自身の最短経路が0でかえってくる。今回のABC191Eのパターン。

※標準ライブラリのわかりやすい記事はこちら
[SciPyでグラフの最短経路を算出（ダイクストラ、ベルマンフォードなど）]
(https://note.nkmk.me/python-scipy-shortest-path/)

#ダイグストラ法
list_Adjは隣接リストです。
隣接リストの作り方は、#使い方の箇所をみてください。

test.py

import heapq,math
def dijkstra(N,list_Adj,start,goal):
    dist = [math.inf]*N
    dist[start] = 0
    # retval = math.inf
    hq = []
    heapq.heappush(hq,(0,start))
    while hq:
        cost,no = heapq.heappop(hq)
        if dist[no]<cost:
            continue
        for g_no,g_cost in list_Adj[no]:
            # if g_no==goal:
            #     retval = min(retval,dist[no]+g_cost)
            if dist[g_no]<=dist[no]+g_cost:
                continue
            dist[g_no] = dist[no]+g_cost
            heapq.heappush(hq,(dist[g_no],g_no))
    return dist[goal]
    # return retval #自分自身への最短経路を算出したい場合はこっちをreturn

#使い方(ABC191Eのコードをそのままはっつけただけ)
N,M = map(int,input().split())

l = [[]*N for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    l[a].append((b,c))
for i in range(N):
    ans = dijkstra(N,l,i,i)
    print(ans if ans!=math.inf else -1)

おわり！