Problem:


All Pairs Shortest Path

Input

An edge-weighted graph G (V, E).

|V| |E|
s0 t0 d0
s1 t1 d1
:
s|E|-1 t|E|-1 d|E|-1

|V| is the number of vertices and |E| is the number of edges in G. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti  represent source and target vertices of i-th edge (directed) and di represents the cost of the i-th edge.

Output

If the graph contains a negative cycle (a cycle whose sum of edge costs is a negative value), print 

NEGATIVE CYCLE

in a line.

Otherwise, print

D0,0 D0,1 ... D0,|V|-1
D1,0 D1,1 ... D1,|V|-1
:
D|V|-1,0 D1,1 ... D|V|-1,|V|-1

The output consists of |V| lines. For each ith line, print the cost of the shortest path from vertex i to each vertex j (j = 0, 1, ... |V|-1) respectively. If there is no path from vertex i to vertex j, print "INF". Print a space between the costs.

Constraints

 1 ≤ |V| ≤ 100

 0 ≤ |E| ≤ 9900

 -2 &times 107 ≤ di ≤ 2 &times 107

 There are no parallel edges

 There are no self-loops

Sample Input 1

4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 7

Sample Output 1

0 1 3 4
INF 0 2 3
INF INF 0 1
INF INF 7 0

Sample Input 2

4 6
0 1 1
0 2 -5
1 2 2
1 3 4
2 3 1
3 2 7

Sample Output 2

0 1 -5 -4
INF 0 2 3
INF INF 0 1
INF INF 7 0

Sample Input 3

4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 -7

Sample Output 3

NEGATIVE CYCLE



Sample input:
4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 7


Sample output:
0 1 3 4
INF 0 2 3
INF INF 0 1
INF INF 7 0

Submission status: Accepted

Solution code:
V,E = map(int,input().split())
dlist = [[0]*V for _ in range(V)]
dp = [[10**11]*V for _ in range(V)]
#0-kの頂点を使ってiからjまで行くときの最短経路
#k-1のときと同じ or i-k+k-j
#初期値はi-j

for _ in range(E):
  el = list(map(int,input().split()))
  dlist[el[0]][el[1]] = el[2]
  dp[el[0]][el[1]] = el[2]

for i in range(V):
  dp[i][i] = 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 range(V):
  for j in range(V):
    if dp[i][j] >= 10**10:
      dp[i][j] = "INF"
      
for i in range(V):
  print(*dp[i])

Submission status: Accepted

Solution code:
"""
ワーシャルフロイド法:O(n^3)
n:頂点数
"""
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

#######################
inf = float('inf')
n, w = [int(x) for x in input().split()] # n:頂点数, w:辺数
d = [[inf]*n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for _ in range(w):
    x, y, z = [int(x) for x in input().split()] # 頂点xと頂点yの間の距離がz
    d[x][y] = z
    # d[y][x] = z # 有向グラフならこの行はコメントアウト
d = warshall_floyd(d)
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit()
for i in d:
    print(" ".join([str(x) for x in i]).replace("inf", "INF"))

Submission status: Accepted

Solution code:
# 入力１
Vn, En = map(int, input().split())

# 初期化
# INF = 10**2 * 10**7  # INF 以外で取りうる値は 10**2 * -10**47< < 10**2 * 10**7
INF = float("inf")
# 入力２：各頂点から別の頂点へ移動する辺とコスト
E = [[INF]*Vn for _ in range(Vn)]
for _ in range(En):
    s, t, c = map(int, input().split())
    E[s][t] = c

for i in range(Vn):
    E[i][i] = 0

for k in range(Vn):
    for i in range(Vn):
        for j in range(Vn):
            E[i][j] = min(E[i][j], E[i][k]+E[k][j])
f = False
for i in range(Vn):
    if E[i][i] < 0:
        f = True
        break
    
if f:
    print("NEGATIVE CYCLE")
else:
    for i in range(Vn):
        for j in range(Vn):
            if E[i][j] == INF:
                E[i][j] = "INF"
        print(" ".join(map(str,E[i])))

Submission status: Accepted

Solution code:
v, e = map(int, input().split())
G = [[float('inf') for _ in range(v)] for i in range(v)]
for i in range(v):
    G[i][i] = 0
# print(G)
dist = [[float('inf') for i in range(v)] for j in range(v)]
for _ in range(e):
    s, t, d = map(int, input().split())
    dist[s][t] = d
for i in range(v):
    dist[i][i] = 0
# print(G)
for k in range(v):
    for i in range(v):
        for j in range(v):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 
            if i == j and dist[i][j] < 0:
                print('NEGATIVE CYCLE')
                exit()
ans = [["INF"]*v for _ in range(v)]
for i in range(v):
    for j in range(v):
        if dist[i][j] != float('inf'):
            ans[i][j] = dist[i][j]
for i in range(v):
    print(*ans[i])

Submission status: Accepted

Solution code:
#Warshall Floyd
N, M = map(int, input().split())
d = [[float('inf')]*N for _ in range(N)]
for i in range(M): #ひとまず枝があるペアは枝の長さをセット
    a,b,t = map(int, input().split())
    d[a][b] = t

for i in range(N):
    d[i][i] = 0 #自身への最短経路は0
#三重ループ
for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])
            if i==j and d[i][i]<0:
                print('NEGATIVE CYCLE')
                exit()

for i in range(N):
    ans = []
    for j in range(N):
        if d[i][j]==float('inf'):
            ans.append('INF')
        else:
            ans.append(str(d[i][j]))
    print(' '.join(ans))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float("inf")

n_nodes, m_edges = map(int, input().split())

edges = [[] for _ in range(n_nodes)]
for _ in range(m_edges):
    s, t, d = map(int, input().split())
    edges[s].append([t, d])
# pprint(edges)


def floyd_warshall(n_nodes, edges):
    dist = [[INF for u in range(n_nodes)] for v in range(n_nodes)]
    for u, e in enumerate(edges):
        for v, cost in e:
            dist[u][v] = cost
    for v in range(n_nodes):
        dist[v][v] = 0
    for k in range(n_nodes):
        for s in range(n_nodes):
            for t in range(n_nodes):
                dist[s][t] = min(dist[s][t], dist[s][k] + dist[k][t])
    return dist


dist = floyd_warshall(n_nodes, edges)
# pprint(dist)

has_negative_cycle = False
for v in range(n_nodes):
    if dist[v][v] < 0:
        has_negative_cycle = True
        break

for u in range(n_nodes):
    for v in range(n_nodes):
        if dist[u][v] == INF:
            dist[u][v] = 'INF'


if has_negative_cycle:
    print('NEGATIVE CYCLE')
else:
    for d in dist:
        print(*d)

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=ja
# Johnsonのアルゴリズム
# Bellman-Ford法で負辺を消去した後、
# 各頂点からダイクストラを行う
from heapq import heappop, heappush
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class BellmanFord:
    """
    shortest_distance(): startノードから各ノードまでの最短距離
    include_negative_cycle(): 負閉路の存在確認
    """
    def __init__(self, V, edges, start):
        """
        V : 頂点数
        edges: (辺の始点,辺の終点,辺のコスト)を要素とする辺のリスト
        start: 始点のノード番号
        """
        self.V = V
        self.edges = edges
        self.start = start

    def include_negative_cycle(self):
        """
        負閉路の存在確認
        Returns: True or False
        """
        d = [0] * self.V
        for i in range(self.V):
            # start, end, cost
            for s, e, c in self.edges:
                if d[e] > d[s] + c:
                    d[e] = d[s] + c
                    # V回目にも更新があるなら負の閉路が存在する
                    if i == self.V-1:
                        return True
        return False
                    
    def shortest_distance(self):
        """ 
        始点から各頂点までの最短距離をを返す
        負閉路に到達可能ならば d[start] = INF
        """
        d = [float('inf')] * self.V
        d[self.start] = 0

        loop_counter = 0
        while True:
            update = False
            # start, end, cost
            for s, e, c  in self.edges:
                if d[s] != float('inf') and d[e] > d[s] + c:
                    d[e] = d[s] + c
                    update = True
            
            # 負閉路の到達しないならばループは高々V-1回
            # ループ回数がV回の時点で更新があるならば負閉路に到達してしまう
            loop_counter += 1
            if loop_counter == self.V and update:
                d[self.start] = float('inf')
                break

            if not update:
                break
        
        return d


class Dijkstra:
    """
    shortest_distance(): startノードから各ノードまでの最短距離
    """
    def __init__(self, graph, start):
        """
        graph: 隣接リストによるグラフ
        start: 始点のノード番号
        """
        self.g = graph
        self.V = len(graph)

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = [float('inf')] * self.V
        self.dist[start] = 0

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (0, start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if dist_u > self.dist[u]:
                continue
            for v, weight in self.g[u]:
                alt = self.dist[u] + weight
                if alt < self.dist[v] :
                    self.dist[v] = alt
                    heappush(self.Q, (alt, v))

    def shortest_distance(self):
        return self.dist


def main():
    V,E,*std = map(int, read().split())

    Edges = []
    for i in range(V):
        Edges.append((V, i, 0))

    for s,t,d in zip(*[iter(std)]*3):
        Edges.append((s, t, d))
    
    # 超頂点からBellman-Ford O(VE)
    bf = BellmanFord(V+1, Edges, V)
    h = bf.shortest_distance()
    
    if float('inf') in h:
        print("NEGATIVE CYCLE")
    else:
        Graph = [[] * V for _ in range(V)]
        for s, t, d in Edges:
            if s == V:
                continue
            else:
                Graph[s].append((t, d + h[s] - h[t]))
        
        ans = []
        # 各頂点からDijkstra O(VElogV)
        for i in range(V):
            d = Dijkstra(Graph, i)
            ans.append(d.shortest_distance())
    
        # 重みを元に戻す O(V^2)
        for i, line in enumerate(ans):
            h_i = h[i]
            for j, n in enumerate(line):
                if n == float('inf'):
                    line[j] = "INF"
                else:
                    line[j] -= h_i - h[j]
            tmp = " ".join(map(str, line))
            print(tmp)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF = float('inf')
V, E = map(int, input().split())
dist = [[INF] * V for _ in range(V)] #dist[i][j]:=iからjまで行く最小距離
for i in range(E):
  s, t, d = map(int, input().split())
  dist[s][t] = d
for j in range(V):
  dist[j][j] = 0
for k in range(V):
  for l in range(V):
    for m in range(V):
      dist[l][m] = min(dist[l][m], dist[l][k]+dist[k][m])
flag = 0
for i in range(V):
  if(dist[i][i] < 0):
    flag = 1
    print('NEGATIVE CYCLE')
    break
if(flag == 0):
  for i in range(V):
    for j in range(V):
      if(dist[i][j] == INF):
        dist[i][j] = 'INF'
    print(*dist[i])

Submission status: Accepted

Solution code:
def warshalFloyd(v,e):
    inf=float("inf")
    G=[[inf if i!=j else 0 for i in range(v)] for j in range(v)]

    for _ in range(e):
        s,t,d=map(int,input().split())
        G[s][t]=d

    for k in range(v):
        for i in range(v):
            for j in range(v):
                G[i][j]=min(G[i][j],G[i][k]+G[k][j])

    return G


v,e=map(int,input().split())
Graph=warshalFloyd(v,e)

for i in range(v):
    if Graph[i][i]<0:
        print("NEGATIVE CYCLE");exit()

for i in range(v):
    Graph[i]=list(map(str,Graph[i]))
    for j in range(v):
        if Graph[i][j]=="inf":
            Graph[i][j]="INF"

for i in range(v):
    print(*Graph[i])

Submission status: Accepted

Solution code:
import sys
import heapq
from collections import deque

# sys.setrecursionlimit(100001)
INF = sys.maxsize


# ===CODE===
def main():
    v, e = map(int, input().split())
    dist_mat = [[INF if i != j else 0 for i in range(v)] for j in range(v)]

    for i in range(e):
        s, t, d = map(int, input().split())
        dist_mat[s][t] = d

    negative = False
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist_mat[i][j] = min(dist_mat[i][j],
                                     dist_mat[i][k] + dist_mat[k][j] if dist_mat[i][k] < INF and dist_mat[k][
                                         j] < INF else INF)
                if i == j and dist_mat[i][j]<0:
                    negative = True
                    print("NEGATIVE CYCLE")
                    exit(0)

    for d in dist_mat:
        for i in range(v):
            if d[i] == INF:
                d[i] = "INF"
        print(*d, sep=" ")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INFTY=float('inf')

def warshallFloyd(l,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                l[i][j]=min(l[i][j],l[i][k]+l[k][j])
    return l

n,e=map(int,input().split())
l=[[INFTY for i in range(n)] for i in range(n)]
for i in range(n):
    l[i][i]=0

for i in range(e):
    a,b,c=map(int,input().split())
    l[a][b]=c

distance=warshallFloyd(l,n)

negative=False

for i in range(n):
    if l[i][i]<0:
        negative=True
        break

if negative:
    print("NEGATIVE CYCLE")
else:
    for i in range(n):
        for j in range(n):
            if j:
                print(" ",end='')
            if l[i][j]==INFTY:
                print("INF",end='')
            else:
                print(l[i][j],end='')
        print()

Submission status: Accepted

Solution code:
v,e = map(int,input().split())
INF = float("INF")
D = [[INF]*v for _ in range(v)]
for i in range(v): D[i][i] = 0
for _ in range(e):
    s,t,d = map(int,input().split())
    D[s][t] = d

for k in range(v):
    for i in range(v):
        if D[i][k] == INF: continue 
        for j in range(v):
            if D[k][j] == INF: continue
            D[i][j] = min(D[i][j],D[i][k]+D[k][j])

neg = False
for i in range(v):
    if D[i][i] < 0:
        neg = True
        break

if neg:
    print("NEGATIVE CYCLE")
else:
    for i in range(v):
            print(" ".join(map(lambda x:"INF" if x == INF else str(x),D[i])))

Submission status: Accepted

Solution code:
V, E = map(int, input().split())
cost = [[float('inf') for _ in range(V)] for _ in range(V)]
for i in range(V):
    cost[i][i] = 0
for _ in range(E):
    s, t, d = map(int, input().split())
    cost[s][t] = d

# print(*cost, sep='\n')
for k in range(V):
    for i in range(V):
        for j in range(V):
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
# print(*cost, sep='\n')
ans = [[] for _ in range(V)]
# ans = str(cost)
# print(*cost[0])
# print(*ans[0])
# print(ans)
ok = True
for i in range(V):
    if cost[i][i] != 0:
        ok = False
if ok:
    for i in range(V):
        for j in range(V):
            if cost[i][j] != float('inf'):
                ans[i].append(cost[i][j])
            else:
                ans[i].append('INF')
    for i in range(V):
        print(*ans[i])
else:
    print('NEGATIVE CYCLE')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

INF = float('inf')
    
def warshall_floyd(V, dist):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

def check_negative_cycle(V, dist):
    dist = warshall_floyd(V, dist)
    
    for i in range(V):
        if dist[i][i] != 0: return dist, True
        
    return dist, False

def main():
    V, E = list(map(int, input().split()))
    
    dist = [[INF for i in range(V)] for j in range(V)]
    
    for i in range(V): dist[i][i] = 0
    
    for i in range(E):
        s, t, d = list(map(int, input().split()))
        dist[s][t] = min(dist[s][t], d)
    
    dist, negative_cycle = check_negative_cycle(V, dist)
    
    if negative_cycle: print('NEGATIVE CYCLE')
    else: 
        for i in range(V):
            for j in range(V):
                if dist[i][j] == INF: dist[i][j] = 'INF'
            print(' '.join(map(str, dist[i])))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
V, E = map(int, input().split())
G = [[] for _ in range(V)]
for _ in range(E):
    s, t, d = map(int, input().split())
    G[s].append((t, d))

dp = [[float('inf')]*V for _ in range(V)]

for i in range(V):
    dp[i][i] = 0
    for j, d in G[i]:
        dp[i][j] = d

# print(*dp, sep='\n')

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, sep='\n')
if all([dp[i][i] == 0 for i in range(V)]):
    for l in dp:
        print(*[d if d != float('inf') else 'INF' for d in l])
else:
    print('NEGATIVE CYCLE')

Submission status: Accepted

Solution code:
v, e = map(int, input().split())

INF = 10 ** 18
d = [[INF]*v for _ in range(v)]

for i in range(e):
    frm, to, dis = map(int, input().split())
    d[frm][to] = dis

for i in range(v):
    d[i][i] = 0

    
for k in range(v):
    for i in range(v):
        for j in range(v):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
            
neg = 0

for i in range(v):
    for j in range(v):
        if d[i][j] + d[j][i]<0:
            neg = 1
            
if neg:
    print('NEGATIVE CYCLE')
else:
    for i in range(v):
        d[i] = [d[i][j] if d[i][j]<INF//10 else 'INF' for j in range(v)]
        print(*d[i])

Submission status: Accepted

Solution code:
V, E = map(int, input().split())
graph = [[10**18]*V for _ in range(V)]

for i in range(V):
    graph[i][i] = 0

for _ in range(E):
    s, t, d = map(int, input().split())
    graph[s][t] = d

for v in range(V):
    for i in range(V):
        for j in range(V):
            graph[i][j] = min(graph[i][j], graph[i][v]+graph[v][j])

ans = True
for i in range(V):
    if graph[i][i]<0:
        ans = False
        break

if ans:
    for g in graph:
        g = [i if not i>10**17 else 'INF' for i in g]
        print(*g)
else:
    print('NEGATIVE CYCLE')

Submission status: Accepted

Solution code:
# 最短経路問題で使われるアルゴリズムの１つ。
# グラフ上の全ての頂点間の最短経路を探す
# 負の閉路（辺の重みの和が負になるような閉路）がない限り、負の辺があっても使える。

# 負の閉路を持つ場合は'NEGATIVE CYCLE'を、そうでない場合には(i,j)成分に
# 頂点iから頂点jへの最短経路の距離を格納するdist_listをprintする関数
def warshall_floyd(v_num, dist_lst):

    # 負の閉路を持つか
    negative_cycle_flag = False

    # 頂点iから頂点jへの経路と、頂点kを経由した場合の経路とを比較して
    # よりコストの合計が小さい方を配列に入れる動的計画法
    for k in range(v_num):
        for i in range(v_num):
            for j in range(v_num):
                # i→k→jがつながっててしかもi→jルートよりもイケてるなら更新
                if dist_lst[i][k] != INF and dist_lst[k][j] != INF:
                    if dist_lst[i][j] > dist_lst[i][k] + dist_lst[k][j]:
                        dist_lst[i][j] = dist_lst[i][k] + dist_lst[k][j]

    for v in range(v_num):
        # dist_lstに負の数が格納されているとは、
        # グラフが負の閉路を持つことを意味する
        if dist_lst[v][v] < 0:
            negative_cycle_flag = True

    if negative_cycle_flag:
        print("NEGATIVE CYCLE")
    else:
        for lst in dist_lst:
            put = ""
            for i in lst:
                if i == INF:
                    put += "INF" + " "
                else:
                    put += str(i) + " "
            print(put.rstrip())

# 頂点の数と辺の数
v_num, e_num = map(int, input().split())

# 配列dist_lst[a][b]には頂点a,b間の辺のコストを入れておき、
# a=bの時は0を、a,b間の辺が存在しないときはINFを入れておく。
INF = 10 ** 20
dist_lst = [[INF] * v_num for _ in range(v_num)]

for _ in range(e_num):
    s, t, dist = map(int, input().split())
    dist_lst[s][t] = dist

for v in range(v_num):
    dist_lst[v][v] = 0

warshall_floyd(v_num, dist_lst)

Submission status: Accepted

Solution code:
V,E = map(int,input().split())
d =[[float('inf')]*V for _ in range(V)]
for i in range(V):
    d[i][i] = 0
for i in range(E):
    s,t,c = map(int,input().split())
    d[s][t] = c

for k in range(V):
    for i in range(V):
        for j in range(V):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

for i in range(V):
    if d[i][i] != 0: #負の閉路が存在するならこのような頂点が存在する
        print('NEGATIVE CYCLE')
        exit()

for i in range(V):
    for j in range(V):
        if d[i][j] == float('inf'):
            d[i][j] = 'INF'
    print(*d[i])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
dp=[[float("inf") for _ in range(N)]for _ in range(N)]
for i in range(N):
    dp[i][i]=0
for _ in range(M):
    s,t,d=map(int,input().split())
    dp[s][t]=d

for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
flag=True
for v in range(N):
    if dp[v][v]<0:
        flag=False
        break

if flag:
    for i in range(N):
        for j in range(N):
            if dp[i][j]==float("inf"):
                dp[i][j]="INF"
    for i in range(N):
        print(*dp[i])
else:
    print("NEGATIVE CYCLE")

Submission status: Accepted

Solution code:
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

##############################
n,w = map(int,input().split()) #n:頂点数　w:辺の数

d = [[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    d[x][y] = z 
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
distance=warshall_floyd(d)

for i in range(n):
    if distance[i][i]<0:
        print('NEGATIVE CYCLE')
        exit()
for i in distance:
    i=['INF' if x==float('inf') else x for x in i]
    print(*i)

Submission status: Accepted

Solution code:
from itertools import product

class FloydWarshall:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self):
        INF = float('inf')
        self.dist = [[INF] * self.N for _ in range(self.N)] # dist[s][t]: the distance of vertex t from s
        self.prev = [[-1] * self.N for _ in range(self.N)] # prev[s][t]: the previous vertex of vertex t on a shortest path from s
        # initialize
        for v in range(self.N):
            self.dist[v][v] = 0; self.prev[v][v] = -1
            for u, c in self.E[v]: self.dist[v][u] = c; self.prev[v][u] = v
        # update
        for k in range(self.N):        
            for i, j in product(range(self.N), repeat=2):
                temp = self.dist[i][k] + self.dist[k][j]
                if self.dist[i][j] > temp: self.dist[i][j] = temp; self.prev[i][j] = self.prev[k][j]
        for v in range(self.N):
            if self.dist[v][v] < 0: return None # There exists a negative cycle
        return self.dist
    
    def shortest_path(self, s, t):
        P = []
        prev_s = self.prev[s]
        while True:
            P.append(t)
            t = prev_s[t]
            if t == -1: break
            elif t == P[0]: P.append(t); break
        return P[::-1]

INF = float('inf')
N, M = map(int, input().split())
fw = FloydWarshall(N)
for _ in range(M):
    a, b, c = map(int, input().split())
    fw.add_edge(a, b, c)
dist = fw.distance()
if dist is None: print('NEGATIVE CYCLE')
else:
    for dst in dist: print(*[d if d != INF else 'INF' for d in dst])

Submission status: Accepted

Solution code:
v, e = map(int, input().split())

adj_mat = [[float("inf")] * v for j in range(v)]
dist = [[float("inf")] * v for j in range(v)]

for i in range(e):
    s, t, d = map(int, input().split())
    # adj_mat[s][t] = d
    dist[s][t] = d

for i in range(v):
    dist[i][i] = 0

for k in range(v):
    for i in range(v):
        for j in range(v):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

for i in range(v):
    if dist[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit()

for i in range(v):
    for j in range(v):
        if dist[i][j] == float("inf"):
            print("INF", end="")
        else:
            print("%d" % (dist[i][j]), end="")

        if j < v - 1:
            print(" ", end="")
    print()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    d = [[0 if i == j else float("inf") for j in range(n)] for i in range(n)]
    for _ in range(m):
        a,b,c = LI()
        d[a][b] = c
    for k in range(n):
        for i in range(n):
            for j in range(n):
                nd = d[i][k]+d[k][j]
                if nd < d[i][j]:
                    d[i][j] = nd
    for i in range(n):
        if d[i][i] < 0:
            print("NEGATIVE CYCLE")
            return
        for j in range(n):
            if d[i][j] == float("inf"):
                d[i][j] = "INF"
    for i in d:
        print(*i,sep = " ")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def warshall_floid(graph: list) -> list:
    """warshall-floid法: 各頂点から各頂点への最短距離を求める
    計算量: O(V^3)
    """
    n = len(graph)
    INF = 10 ** 18
    dp = [[INF] * n for i in range(n)]
    for i in range(n):
        dp[i][i] = 0
    for i in range(n):
        for j, cost in graph[i]:
            dp[i][j] = cost

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  

v, e = map(int, input().split())
info = [list(map(int, input().split())) for i in range(e)]
INF = 10 ** 18

graph = [[] for i in range(v)]
for a, b, cost in info:
    graph[a].append((b, cost))

dp = warshall_floid(graph)

is_negative = False
for i in range(v):
    if dp[i][i] < 0:
        is_negative = True

if is_negative:
    print("NEGATIVE CYCLE")
else:
    for res in dp:
        print(*[num if num < 10**12 else "INF" for num in res])

Submission status: Accepted

Solution code:
import sys


INF = sys.maxsize
V, E = map(int, input().split())

costs = [[INF] * V for _ in range(V)]

for _ in range(E):
  s, t, d = map(int, input().split())
  costs[s][t] = d
  
for i in range(V):
  costs[i][i] = 0
  
for k in range(V):
  for i in range(V):
    for j in range(V):
      if costs[i][k] == INF or costs[k][j] == INF:
        continue
      costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j])

if any(costs[i][i] < 0 for i in range(V)):
  print('NEGATIVE CYCLE')
else:
  for row in costs:
    print(' '.join('INF' if x == INF else str(x)  for x in row))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def check(W):
    # false -> exist negative cycle
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if W[i][k]+W[k][j]+W[j][i]<0:
                    return False
                W[i][j] = min(W[i][j], W[i][k]+W[k][j])
    return True


if __name__ == "__main__":
    V, E = map(int, input().split())
    inf = float("inf")
    W = [[inf]*V for _ in range(V)]
    for i in range(V):
        W[i][i] = 0

    for _ in range(E):
        s, t, d = map(int, input().split())
        W[s][t] = d

    if check(W):
        for i in W:
            print(*(j if j!=inf else "INF" for j in i))
    else:
        print("NEGATIVE CYCLE")

Submission status: Accepted

Solution code:
import math,itertools,bisect,sys,copy,queue
sys.setrecursionlimit(10**7)
INF = 10**20

def LI(): return [int(x) for x in sys.stdin.readline().split()]

N,E = LI()
dp = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N): dp[i][i] = 0
for _ in range(E):
    s,t,d = LI()
    dp[s][t] = d

for k in range(N):
    for i in range(N):
        for j in range(N):
            if dp[i][k] < INF and dp[k][j] < INF:
                dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j])

for i in range(N):
    if dp[i][i] < 0:
        print ('NEGATIVE CYCLE')
        exit(0)
for i in range(N):
    for j in range(N):
        print (dp[i][j] if dp[i][j] < INF else 'INF',end='')
        if j < N-1: print (' ',end='')
    print ('')

Submission status: Accepted

Solution code:
num_V, num_E = map(int, input().split())
INF = float('inf')
E = [[INF] * num_V for _ in range(num_V)]
for _ in range(num_E):
	ts,tt,td = map(int, input().split())
	E[ts][tt] = td
for i in range(num_V):
	E[i][i] = 0

for k in range(num_V):
	for i in range(num_V):
		for j in range(num_V):
			E[i][j] = min(E[i][j], E[i][k]+E[k][j])

cond = 0
for k in range(num_V):
	for i in range(num_V):
		for j in range(num_V):
			if E[i][j] > E[i][k]+E[k][j]:
				cond = 1
				break

if cond == 1:
	print('NEGATIVE CYCLE')
else:
	for e in E:
		print(*['INF' if e[i] == INF else e[i] for i in range(num_V)])

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def warshall_floyd(d):
    """
    d[i][l]がi→lへのコストを示す隣接行列
    結果としてd[i][l]はi→lへの最短コストになる。
    """
    for i in range(len(d)):
        for l in range(len(d)):
            for k in range(len(d)):
                d[l][k] = min(d[l][k], d[l][i] + d[i][k])
    return d


V, E = map(int, input().split())
std = [list(map(int, input().split())) for _ in range(E)]
d = [[INF for _ in range(V)] for _ in range(V)]
for i in range(V):
    d[i][i] = 0
for i in std:
    d[i[0]][i[1]] = i[2]

ans = warshall_floyd(d)
for i in range(V):
    if ans[i][i] < 0:
        print("NEGATIVE CYCLE")
        sys.exit()
for i in range(V):
    for l in range(V):
        if ans[i][l] > 10 ** 11:
            ans[i][l] = "INF"
        else:
            ans[i][l] = str(ans[i][l])

for i in ans:
    print(" ".join(i))

Submission status: Accepted

Solution code:
import sys

def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    has_nagative_cycle = False
    for i in range(n):
        if d[i][i] < 0:
            has_nagative_cycle = True
            break
    for i in range(n):
        d[i][i] = 0
    return has_nagative_cycle

V, E = map(int, sys.stdin.readline().strip().split())

d = [[float("inf") for _ in range(V)] for _ in range(V)]
for i in range(V):
    d[i][i] = 0
for _ in range(E):
    s, t, d_i = map(int, sys.stdin.readline().strip().split())
    d[s][t] = d_i

negative_cycle = warshall_floyd(d, V)
if negative_cycle:
    print("NEGATIVE CYCLE")
else:
    for i in range(V):
        for j in range(V):
            print(d[i][j] if d[i][j] != float("inf") else "INF", end="")
            if j == V - 1:
                print("")
            else:
                print(" ", end="")