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(V, dp):
    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])

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

ncircle = False
for i in range(V):
    if dp[i][i] < 0:#負経路＝ある点から出て自分に帰ってくる経路＝点iから点i
        ncircle = True
if ncircle:
    print('NEGATIVE CYCLE')
else:
    for d in dp:
        print(' '.join(map(str, d)).replace('inf', 'INF'))

Submission status: Accepted

Solution code:
import sys
INFTY=sys.maxsize
#INFTY=2*10**7+1

def readinput():
    nv,ne=list(map(int,input().split()))
    nMap=[]
    for i in range(nv):
        l=[]
        for _ in range(nv):
            l.append(INFTY)
        nMap.append(l)
        nMap[i][i]=0
    for _ in range(ne):
        s,t,d=list(map(int,input().split()))
        nMap[s][t]=d
    return nv,ne,nMap

def warshalFloyd(nv, nMap):
    for k in range(nv):
        for i in range(nv):
            if(nMap[i][k]==INFTY):
                continue
            for j in range(nv):
                if(nMap[k][j]==INFTY):
                    continue
                nMap[i][j] = min(nMap[i][j], nMap[i][k]+nMap[k][j])
    return nMap

def main(nv,ne,nMap):
    nMap=warshalFloyd(nv,nMap)
    #print(nMap)
    isNegative=False
    for i in range(nv):
        if nMap[i][i]<0:
            isNegative=True
    if isNegative==True:
        print('NEGATIVE CYCLE')
    else:
        for i in range(nv):
            for j in range(nv):
                #print(nMap[i][j],INFTY, nMap[i][j]==INFTY)
                if(nMap[i][j]==INFTY):
                    print('INF',end='')
                else:
                    print(nMap[i][j], end='')
                if j==nv-1:
                    print('')
                else:
                    print(' ',end='')
                        

if __name__=='__main__':
    nv,ne,nMap=readinput()
    #print(nMap)
    main(nv,ne,nMap)

Submission status: Accepted

Solution code:
INF=100000000000000
def warshall_floyd(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])

if __name__ == "__main__":
    V,E=map(int,input().split())
    D=[[INF if j!=i else 0 for j in range(V)] for i in range(V)]
    dall=0

    for i in range(E):
        s,t,d=map(int,input().split())
        D[s][t]=d
        if d>=0:
            dall+=d

    warshall_floyd(D)
    flg=False

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

    
    if flg:
        print("NEGATIVE CYCLE")
    else:
        #print('\n'.join(map(str,D[r])))
        for i in range(V):
            print(' '.join(["INF" if j>dall else str(j) for j in D[i]]))

Submission status: Accepted

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

"""Computes all pairs shortest paths in a graph using the Warshall-Floyd algorithm.

Verification: [GRL_1_C]()
"""


import itertools


# the value which represents "infinity."
INF = 10 ** 10


def in_place_warshall_floyd(adj_matrix):
    """Solves the all-pairs shortest path problem using the Warshall-Floyd algorithm.

    The adjacency matrix A of the graph. This object must be
    able to be treated as a $n \times n$ matrix. $A_{i, j}$ represents the
    cost of the edge $i \rightarrow j$. If $A_{i, j}$ is `INF`` or more,
    there is no edge between the two vertices. For all $x$, $A_{x, x} = 0$.
    Note that this matrix will be modified in place during calculation.
    
    Returns: whether the graph has a negative cycle.
    """

    n = len(adj_matrix)
    for k, i, j in itertools.product(range(n), repeat=3):
        if adj_matrix[i][k] == INF or adj_matrix[k][j] == INF:
            continue
        adj_matrix[i][j] = min(adj_matrix[i][j],
                               adj_matrix[i][k] + adj_matrix[k][j])
    return any(adj_matrix[i][i] < 0 for i in range(n))


def dist_to_str(d):
    if d < INF:
        return str(d)
    else:
        return "INF"


def main():
    v, e = (int(z) for z in input().split())
    adj_matrix = [[INF for _ in range(v)] for _ in range(v)]
    for i in range(v):
        adj_matrix[i][i] = 0
    for _ in range(e):
        s, t, d = (int(z) for z in input().split())
        adj_matrix[s][t] = d
    has_nc = in_place_warshall_floyd(adj_matrix)
    if has_nc:
        print("NEGATIVE CYCLE")
    else:
        for line in adj_matrix:
            print(*(dist_to_str(d) for d in line))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

    for k in range(V):
        for i in range(V):
            for j in range(V):
                grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j])
    
    for i in range(V):
        for j in range(V):
            if grid[i][j] < 0 and grid[j][i] < 0:
                print('NEGATIVE CYCLE')
                return
    
    for tmp in grid:
        ans = ['INF' if x == float('inf') else x for x in tmp ]
        print(*ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    V, E = next(it), next(it)
    inf = float("inf")

    dp = [[inf for i in range(V)] for i in range(V)]

    for si, ti, di in zip(it, it, it):
        dp[si][ti] = di
    for i in range(V):
        dp[i][i] = 0

    for s in range(V):
        for t, dts in ((t, dp[t][s]) for t in range(V)):
            if s == t: continue
            for u, (dtu, dsu) in enumerate(zip(dp[t], dp[s])):

                d1 = dts + dsu
                if dtu > d1:
                    if u == t:
                        return print("NEGATIVE CYCLE")
                    dp[t][u] = d1
                    update = True

    for dr in dp:
        print(*["INF" if x == inf else x for x in dr])



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys

def w_f(dp):
    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):
        for j in range(v):
            if dp[i][i] < 0:
                print('NEGATIVE CYCLE')
                sys.exit()
            
            if dp[i][j] == float('inf'):
                dp[i][j] = 'INF'
    return dp

v,e = map(int, input().split())
dp = [[float('inf')]*v for _ in range(v)]
for i in range(e):
    s,t,d = map(int, input().split())
    dp[s][t] = d
    
for i in range(v):
    dp[i][i] = 0
    
res = w_f(dp)
for i in range(v):
    print(*res[i])

Submission status: Accepted

Solution code:
class NegativeWeightDirectedGraph():
    def __init__(self, V):
        self.V = V
        self.INF = 10**10
        self.G = [[self.INF]*V for _ in range(V)]
        for i in range(V):
            self.G[i][i] = 0

    def append(self, src, to, weight):
        self.G[src][to] = weight

    def warshallFloyd(self):
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    if self.G[i][k] != self.INF and self.G[k][j] != self.INF:
                        w = self.G[i][k] + self.G[k][j]
                        self.G[i][j] = min(self.G[i][j], w)
        # check
        for i in range(V):
            if self.G[i][i] < 0:
                return None       
        return self.G

        
V,E = map(int, raw_input().split())
G = NegativeWeightDirectedGraph(V)
for i in range(E):
    s,t,d = map(int, raw_input().split())
    G.append(s,t,d)

ans = G.warshallFloyd()
if ans == None:
    print "NEGATIVE CYCLE"
else:
    for ds in ans:
        print " ".join(map(lambda d: str(d) if d != G.INF else "INF", ds))

Submission status: Accepted

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

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

nega=0
for i in range(V):
    if dp[i][i]<0:
        nega=1
if nega:
    print("NEGATIVE CYCLE")
else:
    for i in range(V):
        if dp[i][0]==float('inf'):
            print("INF",end='')
        else:
            print(dp[i][0],end='')
        for j in range(1,V):
            if dp[i][j]==float('inf'):
                print(" INF",end='')
            else:
                print(" {}".format(dp[i][j]),end='')
        print()

Submission status: Accepted

Solution code:
from copy import deepcopy

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

#M[u][v]:uからvへの重みを保存した隣接行列
INF = 2**36 - 1

M=[[INF]*V for x in range (V)]
for n in range(E):
    input_temp = list(map(int,input().split()))
    M[input_temp[0]][input_temp[1]]=input_temp[2]
    
for v in range(V):
    M[v][v]=0    

def warshallFloyd(M):
    ret = deepcopy(M)
    for k in range(V):
        for i in range(V):
            if ret[i][k] == INF:
                continue
            for j in range(V):
                if ret[k][j] == INF:
                    continue
                ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
    return ret 

def check_negative_cycle(W):
    negative_cycle=False
    for v in range(V):
        if W[v][v] < 0:
            negative_cycle=True
            break
    return negative_cycle

ans=warshallFloyd(M)
negative_cycle=check_negative_cycle(ans)

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

Submission status: Accepted

Solution code:
def warshall_floyd(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])


def check(dp, v):
    for k in range(v):
        for i in range(v):
            for j in range(v):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    return False
    return True


def main():
    v, e = map(int, input().split())
    INF = 10 ** 10
    MAX = 2 * (10 ** 7)
    MIN = -2 * (10 ** 7)
    dp = [[INF for i in range(v)] for j in range(v)]
    for i in range(e):
        s, t, d = map(int, input().split())
        dp[s][t] = d
    for i in range(v):
        for j in range(v):
            if i == j:
                dp[i][j] = 0

    warshall_floyd(dp, v)
    if not check(dp, v):
        print("NEGATIVE CYCLE")
    else:
        for i in range(v):
            for j in range(v):
                if j > 0:
                    print(end=' ') 
                if dp[i][j] > MAX * v or dp[i][j] < MIN * v:
                    print("INF", end='')
                else:
                    print(dp[i][j], end='')
            print()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class WarshallFloyd:
    #O(V^3)で任意２頂点の最短距離
    def __init__(self,n,_first_index=0):
        self.v = n
        self._first_idx=_first_index
        self.d = [[float("INF")]*(n) for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c,directed=0):
        if x == y:
            return False
        f=self._first_idx
        self.d[x-f][y-f] = c
        if directed==0:
            self.d[y-f][x-f] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d
v,e=map(int,input().split())
w=WarshallFloyd(v)
for i in range(e):
    a,s,d=map(int,input().split())
    w.path(a,s,d,1)
d=w.build()
for i in range(v):
    if d[i][i]<0:print("NEGATIVE CYCLE");exit()
for i in d:
    for j in i[:-1]:
        print("INF"if j==float("INF") else j,end=" ")
    print(i[-1]if i[-1]!=float("INF") else "INF")

Submission status: Accepted

Solution code:
from itertools import product

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

INF = 10 ** 10


def _str(n):
    if n == INF:
        return 'INF'
    else:
        return str(n)


def _add(a, b):
    if INF in (a, b):
        return INF
    return a + b


dp = []
for _ in range(V):
    dp.append([INF] * V)

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

for _ in range(E):
    a, b, d = map(int, input().split(' '))
    dp[a][b] = d

for k, i, j in product(range(V), repeat=3):
    dp[i][j] = min(dp[i][j], _add(dp[i][k], dp[k][j]))

results = []
for v in range(V):
    if dp[v][v] < 0:
        print('NEGATIVE CYCLE')
        break
    results.append(' '.join(map(_str, dp[v])))
else:
    print('\n'.join(results))

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=ja
# https://kujira16.hateblo.jp/entry/2014/05/14/220520
# ワーシャルフロイド
import sys
v, e = map(int, input().split())

dist = [[float('inf')] * v for _ in range(v)]

for _ in range(e):
    f, t, d = map(int, input().split())
    dist[f][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):
            # iからjへの最短距離
            # 負の辺がある場合
            if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

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

if negative:
    print('NEGATIVE CYCLE')
    sys.exit()

for i in dist:
    print(' '.join(map(lambda x: 'INF' if x == float('inf') else str(x), i)))
# print(dp)
# print(dist)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
V,E = map(int,input().split())#頂点、辺の数
INF = float("inf")
cost = [[INF]*V for _ in range(V)]#iからjへの重み付き距離cost[i][j]
for i in range(V):
    cost[i][i] = 0
for _ in range(E):
    s,t,dd = map(int,input().split())
    cost[s][t] = dd
#実装
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])
judge = 0
for i in range(V):
    if judge == 1:
        break
    for j in range(i+1,V):
        
        if cost[i][j] + cost[j][i] < 0:
            judge = 1
            break
for i in range(V):
    for j in range(V):
        if cost[i][j] == INF:
            cost[i][j] = "INF"
        else:
            cost[i][j] = str(cost[i][j])
if judge == 1:
    print("NEGATIVE CYCLE")
else:
    for i in range(V):
        print(*cost[i])

Submission status: Accepted

Solution code:
# coding: utf-8
#import numpy as np
import re
import math
from collections import defaultdict
from collections import deque
import collections
from fractions import Fraction
from queue import PriorityQueue
import itertools
from copy import deepcopy
import random
import time
import os
import sys
import datetime
from functools import lru_cache
from functools import reduce
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**19)
class Edge():
    def __init__(self,x,y,cost=1):
        self.x=x
        self.y=y
        self.cost=cost
def yn(b):
    if b:print("yes")
    else:print("no")
def Yn(b):
    if b:print("Yes")
    else:print("No")
def YN(b):
    if b:print("YES")
    else:print("NO")
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def ispow(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n,type="int"):
    if n==0:
        if type=="int":return []
        else:return [False]
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(bbool,ret1,ret2):
    if bbool:return ret1
    else:return  ret2
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def pm(x):
    return x//abs(x)
def inputintlist(): 
    return list(map(int,input().split()))
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def lcm(a,b):
    return a*b//math.gcd(a,b)
    G=[[] for a in range(n)]
    for edge in edges:
        x=edge[0]
        y=edge[1]
        G[x].append(y)
        if mukou:G[y].append(x)
    return G
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.cost))
    return ret
def dijkstra(edges,V,start):
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.cost,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])#[cost,x]
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.cost)#x→yが複数ある場合のためにmin()する
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
                #負閉路検出
                if s==t and mincost[s][t]<0:
                    return "negative cycle"
    return mincost
######################################################################################################
V,E=inputintlist()
edges=[]
for a in range(E):
    e=Edge(*inputintlist())
    edges.append(e)

mincost=warshallfloyd(edges,V)

if mincost=="negative cycle":
    print(mincost.upper())
else:
    for a in range(V):
        for b in range(V):
            if mincost[a][b]==inf:mincost[a][b]="INF"
    for a in range(V):
        print(join(mincost[a]))

Submission status: Accepted

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

for k in range(V):
  for i in range(V):
    for j in range(V):
      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(V):
  if dp[i][i] < 0:
    print('NEGATIVE CYCLE')
    exit()
        
for i in range(V):
  print(*['INF' if d == INF else d for d in dp[i]])

Submission status: Accepted

Solution code:
v, e = map(int, input().split())
g = [[] for _ in range(v)]
dp = [[float("inf")] * v for _ in range(v)]
for i in range(v):
    dp[i][i] = 0
for i in range(e):
    s, t, d = map(int, input().split())
    #g[s].append((d, t))#(重み, 次の頂点)
    dp[s][t] = d

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])
            if i == j and dp[i][j] < 0:
                print("NEGATIVE CYCLE")
                exit()

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

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):
              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])
        #print(d)
    return d

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

d = [[float("INF")] * 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
    #d[y][x] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

D = warshall_floyd(d)
for i in range(n):
  if D[i][i] < 0:
    print("NEGATIVE CYCLE")
    #print(D)
    quit()
    
for i in range(n):
  for j in range(n):
    if D[i][j] == float("inf"):
      if j == n - 1:
        D[i][j] = print("INF")
      else:
        D[i][j] = print("INF", end = " ")
    else:
      if j == n - 1:
        print(D[i][j])
      else:
        print(D[i][j], end = " ")

#print(D)

Submission status: Accepted

Solution code:
V,E = map(int,input().split())
INF = 2*10**10
C = [[INF]*V for _ in range(V)]
for i in range(E):
    tmp = list(map(int,input().split()))
    C[tmp[0]][tmp[1]] = tmp[2]

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

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

negative_cycle_f = False
for i in range(V):
    if C[i][i] < 0:
        negative_cycle_f = True

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

Submission status: Accepted

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

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

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

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

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])
            if i == j and dp[i][i] < 0:
                print("NEGATIVE CYCLE")
                exit()

for i in range(V):
    ans = []
    for j in range(V):
        if dp[i][j] == float("inf"):
            ans.append("INF")
        else:
            ans.append(dp[i][j])
    print(*ans)

Submission status: Accepted

Solution code:
v,e=map(int,input().split())
#隣接行列
INF=float('inf')
D=[[INF]*v for index2 in range(v)]
for index3 in range(v):
    D[index3][index3]=0
for index1 in range(e):
    s,t,d=map(int,input().split())
    D[s][t]=d
    #D[t][s]=d


def warshall_floyd():
    global D

    #kがこの位置でなければならない
    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])
    
    return D

ans=warshall_floyd()
for index4 in range(v):
    if ans[index4][index4]<0:
        print('NEGATIVE CYCLE')
        break
else:
    for index5 in range(v):
        List=[]
        for index6 in range(v):
            if ans[index5][index6]==INF:
                List.append('INF')
            else:
                List.append(ans[index5][index6])
        print(*List)

Submission status: Accepted

Solution code:
INF = float('inf')

V, E = map(int, input().split())
A = [[INF] * V for _ in range(V)]

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

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

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][j], A[i][k] + A[k][j])

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):
        ans_row = []
        for j in range(V):
            if A[i][j] == INF:
                ans_row.append('INF')
            else:
                ans_row.append(A[i][j])
        print(*ans_row)

Submission status: Accepted

Solution code:
import sys, heapq
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 1000000007
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def warshall_floyd(d):
    V = len(d)
    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])
    return d

def resolve():
    V, E = LI()
    con = [[INF]*V for _ in range(V)]
    for _ in range(E):
        s, t, d = LI()
        con[s][t] = d

    ans = warshall_floyd(con)

    has_ns = [ans[i][i]<0 for i in range(V)].count(True)>0
    if has_ns:
        print('NEGATIVE CYCLE')
    else:
        for i in ans:
            print(' '.join([str(j) if j<INF else 'INF' for j in i]))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = float('inf')


def main():
    V, E = map(int, input().split())
    dist = [[0 if i == j else INF for j in range(V)] for i 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):
                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 j in range(V):
            if dist[i][j] == INF:
                dist[i][j] = 'INF'
    for l in dist:
        print(*l)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# n,m = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(sys.stdin.readline() for _ in range(n)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections
N,E = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
#sdw = [[src1 dist1 d1][src1 dist1 d1]...]# vect source1 -> distance1 distances
INF = float("inf")
ALL = set(range(N))

distances = [[INF]*N for _ in range(N)]
for i in range(N):
  distances[i][i] = 0

for i in range(E):
  s,d,w = (map(int,sys.stdin.readline().rstrip().split()))
  distances[s][d] = w

#print(distances)
def warshallFloyd():
  for k in range(N):
    for i in range(N):
      for j in range(N):
        distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])

warshallFloyd()

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

for i in range(N):
  s = []
  for j in range(N):
    if distances[i][j] == INF:
      s.append("INF")
    else:
      s.append(str(distances[i][j]))
  print(" ".join(s))