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:
def warshallFloyd():
    for i in range(V):
        for j in range(V):
            if dp[j][i] == INF: continue
            for k in range(V):
                if dp[i][k] == INF: continue
                dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k])
    return
INF = 10 ** 18
V, E = map(int, input().split())
dp = [[INF for _ in range(V)] for _ in range(V)]
ansF = False
for i in range(V):
    for j in range(V):
        if i == j:
            dp[i][j] = 0


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

warshallFloyd()
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] == INF:
            ptmp = 'INF'
        else:
            ptmp = dp[i][j]
        if j != V - 1:
            print(ptmp, end=' ')
        else:
            print(ptmp)

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
#from collections import Counter,deque
#from operator import itemgetter,mul
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left,bisect_right
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time
#from functools import lru_cache,reduce
#from math import factorial,hypot
#import sys
#from fractions import gcd
setrecursionlimit(10**6)
input=stdin.readline

def main():
    v,e=map(int,input().split())
    INF=2<<31
    d=[[INF]*v for _ in range(v)]
    for _ in range(e):
        s,t,c=map(int,input().split())
        d[s][t]=c
    r=range(v)
    for i in r:d[i][i]=0
    for i in r:
        for j in r:
            for k in r:
                if d[j][i]==INF or d[i][k]==INF:continue
                d[j][k]=min(d[j][k],d[j][i]+d[i][k])

    #for i in d: print(*i)

    for i in r:
        if d[i][i]<0:
            print("NEGATIVE CYCLE")
            exit()

    for i in r:
        for j in r:
            #print(d[i][j],INF,d[i][j]==INF)
            if d[i][j]==INF: d[i][j]="INF"

    for i in d: print(*i)

if __name__=="__main__":main()

Submission status: Accepted

Solution code:
from heapq import heappop,heappush,heapify

class Graph():
    def __init__(self,n,edge,directed=False):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0]].append((e[1],e[2]))
            if not directed:
                self.graph[e[1]].append((e[0],e[2]))
    def warshall_floyd(self,INF=10**18):
        dist = [[INF for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            dist[i][i] = 0
        for i in range(self.n):
            for j,cost in self.graph[i]:
                dist[i][j] = cost
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
        return dist

INF = 10**18

import sys
input = sys.stdin.readline

V,E = map(int,input().split())
edge = [tuple(map(int,input().split())) for _ in range(E)]

g = Graph(V,edge,True)
D = g.warshall_floyd(INF)


for i in range(V):
    for j in range(V):
        if D[i][j] == INF: D[i][j] = 'INF'

for i in range(V):
    if D[i][i] < 0:
        print('NEGATIVE CYCLE')
        break
else:
    print('\n'.join(map(lambda d: ' '.join(map(str,d)),D)))

Submission status: Accepted

Solution code:
def floyd(dismat, v):
    for k in range(v):
        for i in range(v):
            if dismat[i][k] != float("inf"):
                for j in range(v):
                    if dismat[k][j] != float("inf"):
                        dismat[i][j] = min(dismat[i][j], dismat[i][k] + dismat[k][j])
    return dismat


def main():
    ve = input().split()
    v, e = tuple(map(int, ve))
    dismat = [[float("inf") for _ in range(v)] for _ in range(v)]
    for _ in range(e):
        std = input().split()
        s, t, d = tuple(map(int, std))
        dismat[s][t] = d
    for i in range(v):
        dismat[i][i] = 0
    dismat = floyd(dismat, v)
    for i in range(v):
        if dismat[i][i] < 0:
            print("NEGATIVE CYCLE")
            return
    for i in range(v):
        for j in range(v):
            if dismat[i][j] == float("inf"):
                dismat[i][j] = "INF"
        print(" ".join(map(str, dismat[i])))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


INF = 2000000000


def warshallFloyd():
    global V
    for k in range(V):
        for i in range(V):
            if A[i][k] == INF:
                continue
            for j in range(V):
                if A[k][j] == INF:
                    continue
                A[i][j] = min(A[i][k] + A[k][j], A[i][j])
    


nums=list(map(int,input().split()))
V = nums[0]
E = nums[1]

A = [[INF for i in range(V)] for j in range(V)]
for i in range(V):
    A[i][i] = 0

for i in range(E):
    nums=list(map(int,input().split()))
    A[nums[0]][nums[1]] = nums[2]

warshallFloyd()

negative = False

for i in range(V):
    if A[i][i] < 0:
        negative = True

if negative:
    print("NEGATIVE CYCLE")
else:
    for i in range(V):
        for j in range(V):
            if A[i][j] == INF:
                A[i][j] = "INF"
        
    for i in range(V):
        for j in range(V-1):
            if A[i][j] == INF:
                A[i][j] = "INF"
            print(A[i][j], end = " ")
        print(A[i][V-1])

Submission status: Accepted

Solution code:
import heapq

n, m = list(map(int, input().split()))
V = [i for i in range(n)]
E = [{} for _ in range(n)]

for _ in range(m):
    ef, et, ed = list(map(int, input().split()))
    E[ef][et] = ed
    # E[et][ef] = ed

INF = int(1e18)
pred = {i: None for i in range(n)}

d = {i: {j: INF for j in range(n)} for i in range(n)}
for u in range(n):
    d[u][u] = 0
    for v in E[u]:
        d[u][v] = E[u][v]

neg_cycle = False
for k in range(n):
    for u in range(n):
        if d[u][k] == INF:
            continue
        for v in range(n):
            if d[k][v] == INF:
                continue
            if d[u][v] > d[u][k] + d[k][v]:
                d[u][v] = d[u][k] + d[k][v]


for k in range(n):
    if d[k][k] < 0:
        print("NEGATIVE CYCLE")
        exit()

for u in range(n):
    for v in range(n):
        if d[u][v] == INF:
            print("INF", end="")
        else:
            print(d[u][v], end="")
        if v < n - 1:
            print(" ", end="")
    print()

Submission status: Accepted

Solution code:
inf = float('inf')
# ベルマンフォード法 計算量(VE)
# [引数]: 隣接リスト, 始点, 終点
class Bellmanford:
    def __init__(self, to:list, start:int, goal:int = -1):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.goal = goal
        self.dist = [inf] * self.N
        self.dist[start] = 0
        self.exists_negative_cycle = False
        self.exists_negative_cycle_stog = False
        self.is_updated = [False] * self.N

    # distを更新
    def update(self) -> None:
        for _ in range(self.N - 1):
            for v, s in enumerate(self.to):
                if not s: continue
                for nv, w in s:
                    if self.dist[nv] > self.dist[v] + w:
                        self.dist[nv] = self.dist[v] + w

    # グラフの負閉路検出
    def detection(self) -> bool:
        for v, s in enumerate(self.to):
            if not s: continue
            for nv, w in s:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    self.exists_negative_cycle = True
        return self.exists_negative_cycle

    # スタートからゴールまでのパスの負閉路検出
    def detection_stog(self) -> bool:
        for _ in range(self.N):
            for v, s in enumerate(self.to):
                if not s: continue
                for nv, w in s:
                    if self.dist[nv] > self.dist[v] + w:
                        self.dist[nv] = self.dist[v] + w
                        self.is_updated[nv] = True
                    if self.is_updated[v] is True:
                        self.is_updated[nv] = True
        self.exists_negative_cycle_stog = self.is_updated[self.goal]
        return self.exists_negative_cycle_stog

inf = float('inf')
# ワーシャルフロイド法 計算量O(N^3)
# [引数]: 隣接行列
class Warshallfloyd:
    def __init__(self, admat:list):
        self.N = len(admat)
        self.dist = [c[:] for c in admat]

    def update(self) -> None:
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    if i == j:
                        self.dist[i][j] = 0
                    elif self.dist[i][j] > self.dist[i][k] + self.dist[k][j]:
                        self.dist[i][j] = self.dist[i][k] + self.dist[k][j]

N, M = map(int,input().split())
to = [[] for _ in range(N)]
admat = [[inf] * N for _ in range(N)]
for _ in range(M):
    s, t, d = map(int,input().split())
    to[s].append((t, d))
    admat[s][t] = d

BF = Bellmanford(to, 0)
BF.update()
if BF.detection():
    print("NEGATIVE CYCLE")
    exit()
WF = Warshallfloyd(admat)
WF.update()
ans_list = [[-1] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        ans_list[i][j] = WF.dist[i][j] if WF.dist[i][j] != inf else "INF"

for ans in ans_list:
    print(*ans)

Submission status: Accepted

Solution code:
v,e = map(int,input().split())
cost = []
for i in range(v):
    T = [float('inf')]*v
    T[i] = 0
    cost.append(T)
for i in range(e):
    a,b,c = map(int,input().split())
    cost[a][b] = c
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])
flag = True
for i in range(v):
    for j in range(v):
        if cost[i][j] == float('inf'):
            cost[i][j] = 'INF'
        elif i == j and cost[i][j] < 0:
            flag = False
            break
if flag:
    for i in range(v):
        print(' '.join(map(str,cost[i])))
else:
    print('NEGATIVE CYCLE')

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_C
# 螺旋本の説明わかりづらすぎへんか？
# ここでは隣接行列を更新して、i→jに行くときの最短経路としたい(なのでshapeは隣接行列と同じ)

# 操作を理解した後に、螺旋本の証明を読むとわかった気になれる。
# https://qiita.com/okaryo/items/8e6cd73f8a676b7a5d75 このサイトは読んでおくとざっくり操作の概要と仕組みがわかる
# https://triple-four.hatenablog.com/entry/2019/04/02/143939 このサイトでは超丁寧に解説している。お金取れるレベル

from copy import deepcopy

INF = 2**36 - 1


def warchall_floyed(adj_mat: list):
    '''
    隣接行列を受け取る(隣接していないノード間のコストはINFを前提)
    全点間の最短距離を示す行列を返す。
    '''
    n = len(adj_mat)
    ret = deepcopy(adj_mat)
    for k in range(n):  # kは経由を示す。
        for i in range(n):  # iは出発を示す
            if ret[i][k] == INF:
                # ノード同士がつながってなければ更新しない
                continue
            for j in range(n):  # jは終点を示す。
                if ret[k][j] == INF:
                    continue
                ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
                # 直接行ったほうが近いか、kを経由したほうが近いか
    return ret  # 閉路が存在するかどうかは対角成分を見れば良い(自己に戻ってくるのに距離が負ならば負の閉路があるということ)


n_V, n_E = list(map(int, input().split()))
adj_mat = [[INF] * n_V for _ in range(n_V)]  # INFで初期化
# 対角成分だけは0で初期化
for ij in range(n_V):
    adj_mat[ij][ij] = 0
for _ in range(n_E):
    s, t, d = list(map(int, input().split()))
    adj_mat[s][t] = d

ans = warchall_floyed(adj_mat)

# 負のループの調査
for ij in range(n_V):
    if ans[ij][ij] < 0:
        print('NEGATIVE CYCLE')
        exit()

for i in range(n_V):
    for j in range(n_V):
        print(ans[i][j] if ans[i][j] != INF else "INF", end='')
        if j == n_V - 1:
            print()
        else:
            print(' ', end='')

Submission status: Accepted

Solution code:
V,E = map(int,input().split())
INF = 10**20
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):
        for j in range(V):
            if D[i][k] != INF and D[k][j] != INF:
                D[i][j] = min(D[i][j],D[i][k]+D[k][j])

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

if negativecycle:
    print('NEGATIVE CYCLE')
else:
    for i in range(V):
        for  j in range(V):
            if j != 0:
                print(' ',end='')
            if D[i][j] == INF:
                print('INF',end='')
            else:
                print(D[i][j],end='')
        print('')

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import os
import sys


INF = 2 * 10 ** 9 + 1


def main():
    V, E = read_ints()
    G = [[INF] * V for _ in range(V)]
    for _ in range(E):
        s, t, d = read_ints()
        G[s][t] = d
    ans = solve(V, E, G)
    if not ans:
        print('NEGATIVE CYCLE')
    else:
        for a in ans:
            print(*a)


def solve(V, E, G):
    dists = [[INF] * V for _ in range(V)]
    for i in range(V):
        for j in range(V):
            if i == j:
                dists[i][j] = 0
            elif G[i][j] != INF:
                dists[i][j] = G[i][j]

    for k in range(V):
        for i in range(V):
            for j in range(V):
                if (dists[i][k] != INF and dists[k][j] != INF and
                    dists[i][j] > dists[i][k] + dists[k][j]):
                    dists[i][j] = dists[i][k] + dists[k][j]

    for i in range(V):
        if dists[i][i] < 0:
            return None

    for i in range(V):
        for j in range(V):
            if dists[i][j] == INF:
                dists[i][j] = 'INF'
    return dists


###############################################################################
# AUXILIARY FUNCTIONS

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline


def main():
	v, e = map(int, readline().split())
	g = [[1 << 60] * v for _ in range(v)]
	for i in range(v):
		g[i][i] = 0
	for _ in range(e):
		s, t, c = map(int, readline().split())
		g[s][t] = c
	for k in range(v):
		for i in range(v):
			for j in range(v):
				if g[i][j] > g[i][k] + g[k][j]:
					g[i][j] = g[i][k] + g[k][j]
	for i in range(v):
		if g[i][i] < 0:
			print("NEGATIVE CYCLE")
			exit()
	for l in g:
		print(" ".join(["INF" if x > 1 << 40 else str(x) for x in l]))


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import argparse
import sys
inf = float('inf')
from itertools import product


def washall_floyd(d):
    for k, i, j in product(range(n_node), repeat=3):
        d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


def have_negative_loop(dist_mat):
    for i in range(n_node):
        if dist_mat[i][i] < 0:
            return True

    return False


if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument('--input', type=str)
    args = parser.parse_args()
    edge_input = []
    if args.input:
        f = open(args.input, 'r')
        n_node, n_edge = tuple(map(int, f.readline().split()))
        
        if n_node > 0:
            dist_mat = [[inf for _ in range(n_node)] for _ in range(n_node)]
            for _ in range(n_edge):
                from_node, to_node, cost = tuple(map(int, f.readline().split()))
                dist_mat[from_node][to_node] = cost
        f.close()
            
    else:
        n_node, n_edge = tuple(map(int, input().split()))
        dist_mat = \
            [[0 if i==j else inf for i in range(n_node)] for j in range(n_node)]
        if n_edge > 0:            
            for _ in range(n_edge):
                from_node, to_node, cost = tuple(map(int, input().split()))
                dist_mat[from_node][to_node] = cost

    dist_mat = washall_floyd(dist_mat)
    if have_negative_loop(dist_mat):
        print('NEGATIVE CYCLE')
    else:
        for i in range(n_node):
            dist = ' '.join(['INF' if j==inf else str(j) for j in dist_mat[i]])
            print(dist)
            # if i == n_node - 1:
            #     print(dist, end='')
            # else:
            #     print(dist)

Submission status: Accepted

Solution code:
def warshallFloyd():
	for k in range(n):
		for i in range(n):
			if A[i][k] == INF:
				continue
			for j in range(n):
				if A[k][j] == INF:
					continue
				A[i][j] = min(A[i][j], A[i][k] + A[k][j])

INF = 2 * 10**9 + 89

if __name__ == "__main__":
	n, m = map(int, input().split())
	A = [[INF for _ in range(n)] for _ in range(n)]
	for i in range(n):
		A[i][i] = 0
	
	for _ in range(m):
		s, t, d = map(int, input().split())
		A[s][t] = d

	warshallFloyd()

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

	if negative:
		print("NEGATIVE CYCLE")
	else:
		for i in range(n):
			for j in range(n):
				if A[i][j] == INF:
					A[i][j] = "INF"
		for i in range(n):
			print(*A[i])

Submission status: Accepted

Solution code:
# GRL_1_C : ALL Pairs Shortest Path
import sys

debug = False
v, e = map(int, sys.stdin.readline().strip().split())

g = [[float('inf')] * v for _ in range(v)]
for _ in range(e):
    s, t, d = map(int, sys.stdin.readline().strip().split())
    if debug: print('s : {}  t : {}'.format(s, t))
    g[s][t] = d

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

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])

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

if not negative:
    for i in range(v):
        ans = ' '.join(list(map(str, g[i])))
        ans = ans.replace('inf', 'INF')
        print(ans)
else:
    print('NEGATIVE CYCLE')

Submission status: Accepted

Solution code:
# GRL_1_C - All Pairs Shortest Path
def floyd_warshall(dist: "Array[Array[int]]") -> None:
    """
    Compute the shortest paths of all pairs.
    """
    V = len(dist)
    for i in range(V):  # intermediate point
        for j, c2 in enumerate(dist[j][i] for j in range(V)):  #  source
            for k, (c1, c3) in enumerate(zip(dist[j], dist[i])):  # target
                if c2 + c3 < c1:
                    dist[j][k] = c2 + c3


def detect_negative_cycle(dist: "Array[Array[int]]") -> bool:
    return any(d[i] < 0 for i, d in enumerate(dist))


def main():
    N, M, *E = map(int, open(0).read().split())
    dist = [[float("inf")] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0
    for v, u, c in zip(*[iter(E)] * 3):
        dist[v][u] = c
    floyd_warshall(dist)
    if detect_negative_cycle(dist):
        print("NEGATIVE CYCLE")
    else:
        for d in dist:
            cur = [i if i != float("inf") else "INF" for i in d]
            print(" ".join(map(str, cur)))


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def main():
    V, E = map(int, input().split())
    graph = [[INF]*V for _ in range(V)]
    for _ in range(E):
        s, t, d = map(int, input().split())
        graph[s][t] = d
    for i in range(V):
        graph[i][i] = 0
    for k in range(V):
        for i in range(V):
            if graph[i][k] == INF:
                continue
            for j in range(V):
                if graph[k][j] == INF:
                    continue
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    flag = False
    for i in range(V):
        if graph[i][i] < 0:
            flag = True
            break
    if flag:
        print('NEGATIVE CYCLE')
    else:
        for A in graph:
            if A[0] == INF:
                print('INF', end='')
            else:
                print(A[0], end='')
            for i in range(1, V):
                if A[i] == INF:
                    print(' INF', end='')
                else:
                    print(' {}'.format(A[i]), end='')
            print()


if __name__ == '__main__': main()

Submission status: Accepted

Solution code:
lv, le = map(int, input().split())
inf = 1e10

d = [[inf] * lv for _ in range(lv)]
for v in range(lv):
    d[v][v] = 0
for _ in range(le):
    s, t, c = map(int, input().split())
    d[s][t] = c

for k in range(lv):
    for i in range(lv):
        for j in range(lv):
            if d[i][k] < inf and d[k][j] < inf:
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

isneg = False
for v in range(lv):
    if d[v][v] < 0:
        isneg = True
if isneg:
    print('NEGATIVE CYCLE')
else:
    for i in range(lv):
        print(' '.join([str(d[i][j]) if d[i][j] < inf else 'INF' for j in range(lv)]))

Submission status: Accepted

Solution code:
INFTY = 10**13
def floyd():
    for k in range(n):
        for i in range(n):
            if d[i][k] == INFTY:
                continue
            for j in range(n):
                if d[k][j] == INFTY:
                    continue
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

n, e = map(int, input().split())
d = [[0 if i == j else INFTY for j in range(n)]for i in range(n)]

for i in range(e):
    u, v, c = map(int, input().split())
    d[u][v] = c

floyd()

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

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

Submission status: Accepted

Solution code:
import sys

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

Edge = [[] for _ in range(v)]

for i in range(e):
    inpt = list(map(int, input().split( )))
    Edge[inpt[0]].append(inpt[1:])

inf = 10**12


dp = [[inf for _ in range(v)] for __ in range(v)]
for i in range(v):
    for ed in Edge[i]:
        dp[i][ed[0]] = ed[1]
for i in range(v):
    dp[i][i] = 0
"""
・for k,for i, for jの順。for i,j,kだと別物
・dpはkによらず使い回しでよい
"""
for k in range(v):
    for j in range(v):
        for i 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")
        sys.exit()

for i in range(v):
    for j in range(v-1):
        if dp[i][j] >inf//2:###
            print("INF",end = " ")
        else:
            print(dp[i][j], end = " ")
    if dp[i][v-1] >inf//2:
            print("INF",end = "")
    else:
        print(dp[i][v-1], end = "")
    print()

Submission status: Accepted

Solution code:
V, E = map(int, input().split())
INF = 10 ** 10
dp = [[INF for i in range(V)] for j in range(V)]
for i in range(V):
  dp[i][i] = 0

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

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

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

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

Submission status: Accepted

Solution code:
import sys


if __name__ == "__main__":
    V, E = map(lambda x: int(x), input().split())

    dists = [[sys.maxsize for _ in range(V)] for _ in range(V)]
    for i in range(V):
        dists[i][i] = 0

    for _ in range(E):
        s, t, dist = map(lambda x: int(x), input().split())
        if dist < dists[s][t]:
            dists[s][t] = dist

    for t in range(V):
        for s in range(V):
            if sys.maxsize == dists[s][t]:
                continue
            for goal in range(V):
                if sys.maxsize == dists[t][goal]:
                    continue
                if dists[s][t] + dists[t][goal] < dists[s][goal]:
                    dists[s][goal] = dists[s][t] + dists[t][goal]

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

    for dist in dists:
        print(" ".join([str(elem) if sys.maxsize != elem else "INF" for elem in dist]))

Submission status: Accepted

Solution code:
class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # 本来無向グラフでのみ全域木を考えるが、二重辺なら有向でも行けそう
        # d[i][i] < 0 なら、グラフは負のサイクルを持つ
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        hasNegativeCycle = False
        for i in range(self.N):
            if self.d[i][i] < 0:
                hasNegativeCycle = True
                break
        for i in range(self.N):
            self.d[i][i] = 0
        return hasNegativeCycle, self.d


V, E = map(int, input().split())
graph = WarshallFloyd(V)
for i in range(E):
    s, t, d = map(int, input().split())
    graph.add(s, t, d, True)

hasNegativecycle, dist = graph.WarshallFloyd_search()

if hasNegativecycle:
    print("NEGATIVE CYCLE")
    quit()
for row in range(V):
    if dist[row][0] == float('inf'):
        print("INF", end="")
    else:
        print("%d" % (dist[row][0]), end="")
    for col in range(1, V):
        if dist[row][col] == float('inf'):
            print(" INF", end="")
        else:
            print(" %d" % (dist[row][col]), end="")
    print()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    V, E = readi(2)
    G = arr(V, V, fill_value=INF)
    for i in range(V):
        G[i][i] = 0
    for _ in range(E):
        s, t, d = readi(3)
        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])

    for k in range(V):
        for i in range(V):
            for j in range(V):
                if G[i][j] > G[i][k] + G[k][j]:
                    print("NEGATIVE CYCLE")
                    return

    for i in range(V):
        print(" ".join(map(lambda n: "INF" if n == INF else str(n), G[i])))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 30 22:06:02 2019
WarshallFloyd_search
@author: maezawa
"""
import collections


class WarshallFloyd():
    def __init__(self, N):
        self.edges = []
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときは'inf')

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed:
            self.d[u][v] = c
        else:
            self.d[u][v] = c
            self.d[v][u] = c
        if directed:
            self.edges.append([u, v, c])
        else:
            self.edges.append([u, v, c])
            self.edges.append([v, u, c])


    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # 本来無向グラフでのみ全域木を考えるが、二重辺なら有向でも行ける
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        for i in range(self.N):
            self.d[i][i] = 0
        return self.d

    def BellmanFord_negative_bool(self, numNodes, start, zero_indexed=False):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        dd = collections.defaultdict(lambda: float('inf'))
        dd[0] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if dd[e[1]] > dd[e[0]] + e[2]:
                    dd[e[1]] = dd[e[0]] + e[2]
                    if i == numNodes-1:
                        return True
        return False
    

# 使い方の例
        
num_v, num_edges = list(map(int, input().split()))      
graph = WarshallFloyd(num_v)

for i in range(num_edges):
    u,v,w = list(map(int, input().split()))
    graph.add(u, v, w, directed=True)

if graph.BellmanFord_negative_bool(num_v, 0, zero_indexed=True):
    print('NEGATIVE CYCLE')
else:
    result = graph.WarshallFloyd_search()
    for i in range(num_v):
        s = []
        for j in range(num_v):
            if result[i][j] == float("inf"):
                s.append('INF')
            else:
                s.append(str(result[i][j]))
        print(' '.join(s))