ワーシャルフロイド法

今回はワーシャルフロイド法をやっていきます。
使用する問題は以下になります。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=ja

まず、入力から

V,E=map(int,input().split())
INF=10**10
dp=[[INF]*V for _ in range(V)]#隣接行列

for i in range(E):
    s,t,d=map(int,input().split())
    dp[s][t]=d#sからtにいく辺のコスト
    dp[s][s]=0#始点のコストは0

ここでは動的計画法を使っています。
今回のように各辺の情報をまとめたリストを隣接行列をいうらしいです。

続いて処理部分を書いていきます。

for k in range(V):#経由する頂点
    for i in range(V):#始点
        for j in range(V):#終点
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
            print(dp,k,i,j)

for i in range(V):#負の閉路を検出
    if dp[i][i]<0:
        print("NEGATIVE CYCLE")
        exit()

例えば頂点0から頂点2にいく通り方は2種類ある。
パターン1:0-2
パターン2:0-1-2
パターン3:0-3-2
パターン1は入力で重みが与えられているので5と入力されている。
パターン2では頂点1を経由しているので式は、dp[0][2]=min(dp[0][2],dp[0][1]+dp[1][2])となる。
頂点を経由する場合は0-1と1-2のように分けてコストを出す。
パターン3は0-3に辺はないのでコストはINFとなる。

このように各頂点を経由する場合を考え、それらの中でコストが１番低い所を通ることになる。
この処理を各頂点に行う。

負の閉路を検出はdp[i][i]が負の値かによってあるかないかがわかる。
そもそも、始点から始点の距離は0になるはずなので、負の値になるはずがない。

入力例1のグラフ

入力例1の隣接行列

コード全体

V,E=map(int,input().split())
INF=10**10
dp=[[INF]*V for _ in range(V)]#隣接行列

for i in range(E):
    s,t,d=map(int,input().split())
    dp[s][t]=d#sからtにいく辺のコスト
    dp[s][s]=0#始点のコストは0
    

for k in range(V):#経由する頂点
    for i in range(V):#始点
        for j in range(V):#終点
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])

for i in range(V):#負の閉路を検出
    if dp[i][i]<0:
        print("NEGATIVE CYCLE")
        exit()

for i in dp:
    s=" ".join(["INF" if n==INF else str(n) for n in i])
    print(s)

参考記事
https://qiita.com/ageprocpp/items/cdf67e828e1b09316f6e#%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
https://qiita.com/okaryo/items/8e6cd73f8a676b7a5d75