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:
# -*- coding: utf-8 -*-


if __name__ == '__main__':

    n, m = [int(s) for s in input().split()]
    A = [[float("inf") for j in range(n)] for i 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

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

    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):
            print(" ".join(map(lambda x: str(x).upper(), A[i])))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))
 
INF = float("inf")
 
V, E = inpl()
adj = [[] for _ in range(V)]
D = [[INF]*V for _ in range(V)]
 
for _ in range(E):
    s, t, d = inpl()
    D[s][t] = d
 
for v in range(V):
    D[v][v] = 0 

def WarshallFloyd(G):
    V = len(G)
    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

D = WarshallFloyd(D)

for v in range(V):
    if D[v][v] < 0:
        print("NEGATIVE CYCLE")
        break
else:
    for d in range(V):
        print(" ".join(map(str, D[d])).replace("inf", "INF"))

Submission status: Accepted

Solution code:
import queue
import math


def warshall(graph, n):
    for i in range(n):
        graph[i][i] = 0

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

    return graph


def main():
    n, m = map(int, input().split())
    graph = [[float('inf') for _ in range(n)] for _ in range(n)]

    for _ in range(m):
        data = list(map(int, input().split()))

        graph[data[0]][data[1]] = data[2]

    dist = warshall(graph, n)

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

    for i in range(n):
        for j in range(n):

            if j == 0:
                print(dist[i][j] if dist[i][j] != float('inf') else 'INF', end="")
            else:
                print(' {}'.format(dist[i][j] if dist[i][j] != float('inf') else 'INF'), end="")

        print()

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def floyd():
    global d
    global INF
    for k in range(n):
        for i in range(n):
            if (d[i][k] == INF):
                continue
            for j in range(n):
                if (d[k][j] == INF):
                    continue
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);


n,q=[int(x) for x in input().split()]
maxx = 110
INF = 1<< 48
d=[[INF for j in range(n+2)] for i in range(n+2)]

for i in range(n):
    d[i][i] =0
            
for i in range(q):    
    s=[int(x) for x in input().split()]
    d[s[0]][s[1]]=s[2]
    
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 (d[i][j] == INF):
                if j==n-1:print("INF")
                else: print("INF",end=' ')
            else:
                if j!=n-1:print("%d"%(d[i][j]),end=' ')
                else: print("%d"%(d[i][j]))

Submission status: Accepted

Solution code:
"""
Warshall-Floyd
"""

INF = 10 ** 20

v_num, e_num = map(int, input().split())
dist_lst = [[INF] * v_num for _ in range(v_num)]
negative_cycle_flag = False
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

for k in range(v_num):
  for i in range(v_num):
    for j in range(v_num):
      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):
  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())

Submission status: Accepted

Solution code:
V, E = list(map(int, input().split(' ')))
A = [[float('inf') if i != j else 0 for i in range(V)] for j in range(V)]
for i in range(E):
    s, t, d = list(map(int, input().split(' ')))
    A[s][t] = d

def warchall_floyd():
    global A
    for k in range(V):
        for i in range(V):
            if A[i][k] == float('inf'): continue
            for j in range(V):
                if A[k][j] == float('inf'): continue
                A[i][j] = min(A[i][j], A[i][k] + A[k][j])
                if i == j and A[i][i] < 0: return False
    return True

if warchall_floyd():
    for i in range(V):
        print(' '.join([str(x) if x != float('inf') else 'INF' for x in A[i]]))
else:
    print('NEGATIVE CYCLE')

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    graph = [[INF] * N for _ in range(N)]
    for _ in range(M):
        s, t, c = il()
        graph[s][t] = c
    for n in range(N):
        graph[n][n] = 0

    # ワーシャルフロイド
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if graph[i][k] == INF or graph[k][j] == INF: continue
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

    # 回答
    ret = []
    for n in range(N):
        if graph[n][n] < 0:
            # 自身までの距離が負の場合
            # (負の閉路が存在する場合）
            print('NEGATIVE CYCLE')
            exit()
        tmp = []
        for d in graph[n]:
            if d == INF:
                tmp.append('INF')
            else:
                tmp.append(d)
        ret.append(tmp)
    else:
        for r in ret:
            print(*r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
V,E = map(int,input().split())
cost_matrix = [[float('inf')]*V for _ in range(V)]
for i in range(V):
    cost_matrix[i][i] = 0
for i in range(E):
    start,end,cost = map(int,input().split())
    cost_matrix[start][end] = cost
for stop in range(V):
    for start in range(V):
        for end in range(V): 
            cost_matrix[start][end] = min(cost_matrix[start][end],cost_matrix[start][stop]+cost_matrix[stop][end])
is_negative = False
for start in range(V):
    for end in range(V):
        if cost_matrix[start][end] < 0 and start == end:
            is_negative = True
        elif cost_matrix[start][end] == float('inf'):
            cost_matrix[start][end] = 'INF'
if is_negative:
    print('NEGATIVE CYCLE')
else:
    for start in range(V):
        res = list(map(str,cost_matrix[start]))
        print(' '.join(res))

Submission status: Accepted

Solution code:
from sys import stdin, exit
input = stdin.readline


INFTY = 2 ** 40
lines = stdin.readlines()
v, e = list(map(int, lines[0].split()))

A = [[INFTY] * v for i in range(v)]
#shokika
for i in range(v):
    A[i][i] = 0

for i in range(e):
    s, t, d = list(map(int, lines[i+1].split()))
    A[s][t] = d

for k in range(v):
    for i in range(v):
        if A[i][k] == INFTY:
            continue
        for j in range(v):
            if A[k][j] == INFTY:
                continue
            a = A[i][j]
            b = A[i][k] + A[k][j]
            if a > b:
                A[i][j] = b

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


for i in range(v):
    for j in range(v):
        if j < (v-1):
            if A[i][j] == INFTY:
                print('INF', end=' ')
            else:
                print(A[i][j], end=' ')
        else:
            if A[i][j] >= INFTY:
                print('INF')
            else:
                print(A[i][j])

Submission status: Accepted

Solution code:
INF = 10 ** 20
V, E = map(int, input().split())
graph = [[INF] * 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 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])

negative = 0
for i in range(V):
    if graph[i][i] < 0:
      negative = 1
      break

if negative == 1:
  print("NEGATIVE CYCLE")
else:
  for i in range(V):
    for j in range(V):
      if graph[i][j] == INF:
        print("INF", end = "")
      else:
        print("{}".format(graph[i][j]), end = "")
      if j != V-1:
        print(" ", end = "")
    print()

Submission status: Accepted

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

inf = float("inf")

#edgesをdp的に用いる
edges = [[inf]*v for _ in range(v)]
for _ in range(e):
    s, t, d = map(int, input().split())
    edges[s][t] = d

for w in range(v):
    edges[w][w] = 0

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


if any(edges[i][i] < 0 for i in range(v)):
    print("NEGATIVE CYCLE")
else:
    for x in edges:
        x = ["INF" if y == inf else str(y) for y in x]
        print(" ".join(x))

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, 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] != float("INF") and D[k][j] != float("INF"):
                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:
import sys
inf=float("inf")  

icase=0
if icase==0:
    nv,ne=map(int,input().split())
    dp=[[inf]*nv for i in range(nv)] 

    for i in range(ne):
        si,ti,di=map(int,input().split())
        dp[si][ti]=di
elif icase==1:
    nv,ne=4,6
    dp=[[inf,1,5,inf], [inf,inf,2,4], [inf,inf,inf,1], [inf,inf,7,inf]]    
elif icase==2:
    nv,ne=4,6
    dp=[[inf,1,-5,inf], [inf,inf,2,4], [inf,inf,inf,1], [inf,inf,7,inf]]    
elif icase==3:
    nv,ne=4,6
    dp=[[inf,1,5,inf], [inf,inf,2,4], [inf,inf,inf,1], [inf,inf,-7,inf]]
for i in range(nv):
    dp[i][i]=0

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


for i in range(nv):
    if dp[i][i]<0:
        print("NEGATIVE CYCLE")
        sys.exit()
for i in range(nv):
    for j in range(nv):
        if dp[i][j]==inf:
            dp[i][j]="INF"
for i in range(nv):
    for j in range(nv-1):
        print(dp[i][j],end=" ")
    print(dp[i][nv-1])

Submission status: Accepted

Solution code:
V, E = map(int, input().split())

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

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

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

for k in range(V):
    for i in range(V):
        for j in range(V):
            dists[i][j] = min(dists[i][j], dists[i][k]+dists[k][j])
            if i == j and dists[i][j] < 0:
                print('NEGATIVE CYCLE')
                exit()

for row in dists:
    print(' '.join(['INF' if d == float('inf') else str(d) for d in row]))

Submission status: Accepted

Solution code:
def warshall_floyd():
    for k in range(n):
        for i in range(n):
            for j in range(n):
                A[i][j] = min(A[i][j],A[i][k]+A[k][j])
    return

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

negative_flag = False
for i in range(n):
    if A[i][i]<0:
        negative_flag = True
        
for i in range(n):
    for j in range(n):
        if A[i][j] == float("inf"):
            A[i][j] = 'INF'
        
if negative_flag:
    print("NEGATIVE CYCLE")
else:
    for i in range(n):
        print(' '.join(map(str,A[i])))

Submission status: Accepted

Solution code:
def warshall_floyd():
    inf=float("inf")
    v,e=map(int,input().split())
    #頂点集合、始点、終点
    dp=[[[inf]*v for i in range(v)] for j in range(v+1)]

    #initialize
    for i in range(v):
        dp[0][i][i]=0
    for _ in range(e):
        s,t,d=map(int,input().split())
        dp[0][s][t]=d
    
    for i in range(1,v+1):
        for j in range(v):
            for k in range(v):
                dp[i][j][k]=min(dp[i-1][j][k],dp[i-1][j][i-1]+dp[i-1][i-1][k])
    
    #負閉路判定
    for i in range(v):
        if dp[v][i][i]<0 :
            print("NEGATIVE CYCLE")
            return None
    
    for i in range(v):
        print(" ".join(["INF" if x ==inf else str(x) for x in dp[v][i]]))

warshall_floyd()

Submission status: Accepted

Solution code:
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(v):
        for i in range(v):
            for j in range(v):
                if d[i][k]!=float('inf') and d[k][j]!=float('inf'):
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

v,e = map(int,input().split())
d = [[float('inf')]*v for i in range(v)] 
for i in range(e):
    x,y,z = map(int,input().split())
    d[x][y] = z
for i in range(v):
    d[i][i] = 0 #自身のところに行くコストは０
d=warshall_floyd(d)
for i in range(v):
    if d[i][i]<0:
        print('NEGATIVE CYCLE')
        exit()
ans=[['']*v for _ in range(v)]
for i in range(v):
    for j in range(v):
        if d[i][j]==float('inf'):
            ans[i][j]='INF'
        else:
            ans[i][j]=str(d[i][j])
for i in range(v):
    print(*ans[i],sep=' ')

Submission status: Accepted

Solution code:
def floyd_warshall(dp, V):
    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])

    # Check Negative Cycle
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    return -1
    return dp

INF = float('inf')
V, E = [int(x) for x in input().split()]
dp = [[INF for _ in range(V)] for _ in range(V)]
for i in range(V):
    dp[i][i] = 0

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

dp = floyd_warshall(dp, V)
if dp == -1:
    print("NEGATIVE CYCLE")
else:
    for i in range(V):
        for j in range(V):
            if dp[i][j] == INF:
                dp[i][j] = "INF"
        print(*dp[i])

Submission status: Accepted

Solution code:
# https: // onlinejudge.u-aizu.ac.jp/problems/GRL_1_C
INF = float('inf')

V, E = list(map(int, input().split()))

D = [[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 = list(map(int, input().split()))
    D[s][t] = d

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

has_negative_cycle = False
for i in range(V):
    for j in range(V):
        if i == j and D[i][j] < 0:
            has_negative_cycle = True
        if D[i][j] == INF:
            D[i][j] = 'INF'
        else:
            D[i][j] = str(D[i][j])


if has_negative_cycle:
    print('NEGATIVE CYCLE')
else:
    for row in D:
        print(' '.join(row))

Submission status: Accepted

Solution code:
vn,en = map(int,input().split())
dis = [[float("inf") for __ in range(vn)] for _ in range(vn)]
for i in range(vn):
    dis[i][i] = 0
for _ in range(en):
    s,t,d = map(int,input().split())
    dis[s][t] = d
for k in range(vn):
    for i in range(vn):
        for j in range(vn):
            dis[i][j] = min(dis[i][k]+dis[k][j], dis[i][j])
            if i==j:
                if dis[i][j]<0:
                    print('NEGATIVE CYCLE')
                    exit()
for i in range(vn):
    ans = []
    for j in range(vn):
        if dis[i][j] == float('inf'):
            ans.append('INF')
        else:
            ans.append(str(dis[i][j]))
    print(' '.join(ans))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, M = map(int, input().split())
    INF = float('inf')
    D = [[INF]*N for _ in [0]*N]
    for _ in [0]*M:
        a, b, c = map(int, input().split())
        D[a][b] = c

    for i in range(N):
        D[i][i] = 0

    for i in range(N):
        for j in range(N):
            for k in range(N):
                d = D[j][i]+D[i][k]
                if D[j][k] > d:
                    D[j][k] = d

    for i in range(N):
        if D[i][i] < 0:
            print('NEGATIVE CYCLE')
            return

    for d in D:
        print(' '.join(map(lambda x: str(x) if x < INF else 'INF', d)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

INF = float('inf')

v,e = mi()
dp = [[float('inf') for i in range(v)] for j in range(v)]

path = [[] for i in range(v)]
for i in range(e):
    s,t,d = mi()
    path[s].append((t,d))
    dp[s][t] = d

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')
        break
else:
    for i in range(v):
        for j in range(v):
            c = dp[i][j]
            if c == INF:
                c = 'INF'
            if j != v-1:
                print(c,end=" ")
            else:
                print(c)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    V, E = map(int, input().split())
    cost = [[f_inf] * 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

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

    for i in range(V):
        for j in range(V):
            if i == j and cost[i][j] < 0:
                print("NEGATIVE CYCLE")
                exit()
            if cost[i][j] == f_inf:
                cost[i][j] = "INF"

    for res in cost:
        print(*res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def main():
    V, E = map(int, input().split())
    G = [[float("INF")] * V for _ in range(V)]
    for i in range(V):
        G[i][i] = 0
    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]) 

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

        for j in range(V):
            if G[i][j] == float("INF"):
                G[i][j] = "INF"
    for g in G:
        print(*g)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
V,E = map(int,input().split())
matrix = [ [float('inf')]*V for _ in range(V) ]

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

for _ in range(E):
  u,v,w = map(int,input().split())
  matrix[u][v] = w

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

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


for i in range(V):
  print(" ".join(map(str, [ "INF" if e==float('inf') else e for e in matrix[i] ])))

Submission status: Accepted

Solution code:
V, E = map(int, input().split())
inf = float('inf')
dps = [[inf for _ in range(V)] for _ in range(V)]

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


for i in range(V):
    dps[i][i] = 0
for v in range(V):
    for i in range(V):
        for j in range(V):
            dps[i][j] = min(dps[i][j], dps[i][v] + dps[v][j])
# print(dps)
flag = False
for i in range(V):
    if dps[i][i] < 0:
        flag = True
if flag:
    print('NEGATIVE CYCLE')
else:
    for dp in dps:
        print(*['INF' if num == inf else num for num in dp])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
INF=10**18
dis=[[INF for _ in range(n)]for _ in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  dis[a][b]=c
for i in range(n):
  dis[i][i]=0
for k in range(n):
  for i in range(n):
    for j in range(n):
      dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])
for i in range(n):
  for j in range(n):
    if dis[i][j]>=10**10:dis[i][j]='INF'
  if dis[i][i]<0:
    print('NEGATIVE CYCLE')
    exit()
for i in dis:
  print(*i)

Submission status: Accepted

Solution code:
import sys
import bisect
import math
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from operator import itemgetter
inf=10**20
v,e=map(int,readline().split())
#print(v,e)
d=[[inf for j in range(v)] for i in range(v)]
for i in range(v):
    d[i][i]=0
for i in range(e):
    a,b,c=map(int,readline().split())
    d[a][b]=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])
ng=0
for i in range(v):
    if d[i][i]<0:
        ng=1
        break
#print(d[2])

if ng:
    print("NEGATIVE CYCLE")
else:
    for i in range(v):
        ans=""
        for j in range(v):
            if d[i][j]>2e9:
                ans+="INF"+" "
            else:
                ans+=str(d[i][j])+" "
        print(ans.rstrip())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
	V,E = map(int,input().split())
	dist = [[INF]*V for _ in range(V)]
	for _ in range(E):
		s,t,d = map(int,input().split())
		dist[s][t] = d
	
	for k in range(V):
		for i in range(V):
			for j in range(V):
				if dist[i][k] != INF and dist[k][j] != INF and dist[i][j] > dist[i][k] + dist[k][j]:
					dist[i][j] = dist[i][k] + dist[k][j]
	
	for i in range(V):
		if dist[i][i] < 0:
			print('NEGATIVE CYCLE')
			return
		dist[i][i] = 0
	
	for i in range(V):
		print(' '.join(map(lambda x:'INF' if x == INF else str(x),dist[i])))
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
V,E = list(map(int,input().split()))
STD = [list(map(int,input().split())) for _ in range(E)]

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

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

for std in STD:
    D[std[0]][std[1]] = std[2]

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 d in D:
    print(*list(map(lambda x: str(x) if x != float('inf') else 'INF', d)))

Submission status: Accepted

Solution code:
from math import isinf

V, E = map(int, input().split())
d = [[float('inf') for i in range(V)] for j in range(V)]

for i in range(V):
    d[i][i] = 0
    
for i in range(E):
    s, t, w = map(int,input().split())
    d[s][t] = w
    
for k in range(V):
    for j in range(V):
        for i in range(V):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
            
for i in range(V):
    if d[i][i] < 0:
        print('NEGATIVE CYCLE')
        exit()

for di in d:
    print(' '.join( ('INF' if isinf(dij) else str(dij) for dij in di)))

Submission status: Accepted

Solution code:
# 60

v, e = map(int, input().split())
dp = [[[float("Inf")] * (v) for x in range(v)] for y in range(v+1)]

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

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

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

for i in range(v):
    if dp[v][i][i] < 0:
        print("NEGATIVE CYCLE")
        break
else:
    for i in range(v):
        print(*[(str(x)).upper() for x in dp[v][i]])

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

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

# 負の閉路の検出。自分自身への最短路が負
for i in range(V):
    if C[i][i] < 0:
        print('NEGATIVE CYCLE')
        exit()

ans = []
for i in range(V):
    tmp = []
    for j in range(V):
        if C[i][j] == float('inf'):
            tmp.append('INF')
        else:
            tmp.append(C[i][j])
    ans.append(tmp)

for i in range(V):
    print(*(ans[i]))

Submission status: Accepted

Solution code:
v,e=map(int,input().split())
dis=[[10**15 for _ in range(v)]for _ in range(v)]
for i in range(e):
	a,b,c=map(int,input().split())
	dis[a][b]=c
for i in range(v):
	dis[i][i]=0
for k in range(v):
	for i in range(v):
		for j in range(v):
			dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])
for i in range(v):
	if dis[i][i]<0:
		print("NEGATIVE CYCLE")
		exit()
for i in range(v):
	ans=[]
	for j in range(v):
		if dis[i][j]>=10**14:
			ans.append("INF")
		else:
			ans.append(dis[i][j])
	print(*ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

v, e = map(int, input().split())
INF = float("inf")
dist = [[INF for _ in range(v)] for _ in range(v)]
for i in range(e):
    s, t, d = map(int, input().split())
    dist[s][t] = d

for k in range(v):
    for i in range(v):
        for j in range(v):
            if i == j:
                dist[i][j] = 0
            elif dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

# check negative cycle
has_negative = False
for k in range(v):
    for i in range(v):
        for j in range(v):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                has_negative = True
                break
if has_negative:
    print("NEGATIVE CYCLE")
    exit()

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

Submission status: Accepted

Solution code:
INF = 2**120

import copy
import sys

V, E = map(int, input().split())
d = [[INF for i in range(V)] for j in range(V)]
for i in range(E):
    s, t, dis = map(int, input().split())
    d[s][t] = 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])

d1 = copy.deepcopy(d)

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

for i in range(V):
    for j in range(V):
        if d[i][j] != d1[i][j]:
            print('NEGATIVE CYCLE')
            sys.exit()

for i in range(V):
    for j in range(V):
        if d[i][j] > 2**60:
            d[i][j] = 'INF'

for i in range(V):
    print(' '.join([str(j) for j in d[i]]))

Submission status: Accepted

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

def floyd_warshall(dist):                                               # 動的計画法。頂点 k まで経由することが可能な場合の最短距離という部分問題を考えて、k = 0 から漸化式的に計算する
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]                # dist は頂点 k までを経由した場合の最短距離。dist[i][k]は k を経由することは無いので、dist[i][k]は k ステップ目で更新されることはない。
                                                                        # よって、min の中身は全て k-1 ステップ目の情報で構成されており、漸化式となっている。
    return dist

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

INF = float("inf")

dist = [[INF] * V for _ in range(V)]                           # 辺が存在しない事をコスト無限大で表現
for _ in range(E):
    i,j,weight = map(int,input().split())
    # i -= 1                                                            # 番号のデクリメントが必要な場合、コメントアウトを消す
    # j -= 1
    dist[i][j] = weight
    # dist[j][i] = weight                                               # 無向グラフの場合はコメントアウトを消す
for i in range(V):
    dist[i][i] = 0                                                      # 自身のところに行くコストは０

d = floyd_warshall(dist)                                                # 各点間の距離が隣接行列の形で与えられる

nagativity = False                                                      # 負のサイクルかどうかを判定
for i in range(V):
    if d[i][i] < 0:
        nagativity = True
if nagativity:
    print('NEGATIVE CYCLE')
else:
    for a in d:
        print(*[x if x != INF else "INF" for x in a])              # inf をどのように記述するかを指定