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:
#!/usr/bin/python
import sys,heapq

INF=2000000000000
def shortestPath(g,dist,prev):
	n = len(g)-1
	h = [INF]*n+[0]
	for k in range(n+1):
		for i in range(n+1):
			for e in g[i]:
				if h[e[1]]<INF and e[0]<INF and h[e[2]] > h[e[1]] + e[0]:
					h[e[2]] = h[e[1]] + e[0]
					if k==n: return False # negative cycle
	for i in range(n):
		for e in g[i]:
			e[0]+=h[i]-h[e[2]]
	for s in range(n):
		Q=[]
		heapq.heappush(Q,[0,s,s])
		while Q:
			e = heapq.heappop(Q)
			if prev[s][e[2]]!=-2: continue
			prev[s][e[2]] = e[1]
			for f in g[e[2]]:
				if e[0]<INF and f[0]<INF and dist[s][f[2]] > e[0] + f[0]:
					dist[s][f[2]] = e[0] + f[0]
					heapq.heappush(Q,[(e[0] + f[0]),f[1],f[2]])
		for u in range(n):
			if dist[s][u]<INF: dist[s][u] += h[u] - h[s]
	return True

V,E=map(int,raw_input().split())
g=[[] for i in range(V+1)]
dist=[[INF]*V for i in range(V)]
prev=[[-2]*V for i in range(V)]
for i in range(V): g[i].append([0,i,i])
for i in range(V): g[V].append([0,V,i])
for i in range(E):
	s,t,e=map(int,raw_input().split())
	g[s].append([e,s,t])
if not shortestPath(g,dist,prev):
	print("NEGATIVE CYCLE")
else:
	for i in range(V):
		print(' '.join("INF" if dist[i][j]>=INF else str(dist[i][j]) for j in range(V)))

Submission status: Accepted

Solution code:
#!/usr/bin/python
import sys,heapq
if 'pypy' in sys.version.lower():
	import rpython.rlib.streamio
	stream=rpython.rlib.streamio.fdopen_as_stream(sys.stdin.fileno(),'r')
	raw_input=stream.readline
	def cmp_lt(x,y): return x < y
	heapq.cmp_lt=cmp_lt
elif sys.version_info[0]>=3: raw_input=input

INF=1234567890123456789
COMPILE=123456789012
def compile(a,b,c):
	return ((a+COMPILE)<<18) | (b<<9) | c
def decompile(a):
	return ((a>>18)-COMPILE,(a>>9)&511,a&511)

def shortestPath(g,dist,prev):
	n = len(g)-1
	h = [INF]*n+[0]
	for k in range(n+1):
		for i in range(n+1):
			for e in g[i]:
				if h[e[1]]<INF and e[0]<INF and h[e[2]] > h[e[1]] + e[0]:
					h[e[2]] = h[e[1]] + e[0]
					if k==n: return False # negative cycle
	for i in range(n):
		for e in g[i]:
			e[0]+=h[i]-h[e[2]]
	for s in range(n):
		Q=[]
		heapq.heappush(Q,compile(0,s,s))
		while Q:
			e = decompile(heapq.heappop(Q))
			if prev[s][e[2]]!=-2: continue
			prev[s][e[2]] = e[1]
			for f in g[e[2]]:
				if e[0]<INF and f[0]<INF and dist[s][f[2]] > e[0] + f[0]:
					dist[s][f[2]] = e[0] + f[0]
					heapq.heappush(Q,compile(e[0]+f[0],f[1],f[2]))
		for u in range(n):
			if dist[s][u]<INF: dist[s][u] += h[u] - h[s]
	return True

def entry_point(argv):
	V,E=[int(e) for e in raw_input().rstrip().split(' ')]
	g=[[] for i in range(V+1)]
	dist=[[INF]*V for i in range(V)]
	prev=[[-2]*V for i in range(V)]
	for i in range(V): g[i].append([0,i,i])
	for i in range(V): g[V].append([0,V,i])
	for i in range(E):
		s,t,e=[int(e) for e in raw_input().rstrip().split(' ')]
		g[s].append([e,s,t])
	if not shortestPath(g,dist,prev):
		print("NEGATIVE CYCLE")
	else:
		for i in range(V):
			print(' '.join(["INF" if dist[i][j]>=INF else str(dist[i][j]) for j in range(V)]))
	return 0

def target(*args):
	return entry_point, None

if __name__ == '__main__': entry_point([])

Submission status: Accepted

Solution code:
#!/usr/bin/python
import sys,heapq
if 'pypy' in sys.version.lower():
	import rpython.rlib.streamio
	stream=rpython.rlib.streamio.fdopen_as_stream(sys.stdin.fileno(),'r')
	raw_input=stream.readline
	def cmp_lt(x,y): return x < y
	heapq.cmp_lt=cmp_lt
	COMPILE=123456789012
	def compile(a,b,c):
		return ((a+COMPILE)<<18) | (b<<9) | c
	def decompile(a):
		return ((a>>18)-COMPILE,(a>>9)&511,a&511)
else:
	def compile(a,b,c):
		return (a,b,c)
	def decompile(a):
		return a
	if sys.version_info[0]>=3: raw_input=input

INF=1234567890123456789
def shortestPath(g,dist,prev):
	n = len(g)-1
	h = [INF]*n+[0]
	for k in range(n+1):
		for i in range(n+1):
			for e in g[i]:
				if h[e[1]]<INF and e[0]<INF and h[e[2]] > h[e[1]] + e[0]:
					h[e[2]] = h[e[1]] + e[0]
					if k==n: return False # negative cycle
	for i in range(n):
		for e in g[i]:
			e[0]+=h[i]-h[e[2]]
	for s in range(n):
		Q=[]
		heapq.heappush(Q,compile(0,s,s))
		while Q:
			e = decompile(heapq.heappop(Q))
			if prev[s][e[2]]!=-2: continue
			prev[s][e[2]] = e[1]
			for f in g[e[2]]:
				if e[0]<INF and f[0]<INF and dist[s][f[2]] > e[0] + f[0]:
					dist[s][f[2]] = e[0] + f[0]
					heapq.heappush(Q,compile(e[0]+f[0],f[1],f[2]))
		for u in range(n):
			if dist[s][u]<INF: dist[s][u] += h[u] - h[s]
	return True

def entry_point(argv):
	V,E=[int(e) for e in raw_input().rstrip().split(' ')]
	g=[[] for i in range(V+1)]
	dist=[[INF]*V for i in range(V)]
	prev=[[-2]*V for i in range(V)]
	for i in range(V): g[i].append([0,i,i])
	for i in range(V): g[V].append([0,V,i])
	for i in range(E):
		s,t,e=[int(e) for e in raw_input().rstrip().split(' ')]
		g[s].append([e,s,t])
	if not shortestPath(g,dist,prev):
		print("NEGATIVE CYCLE")
	else:
		for i in range(V):
			print(' '.join(["INF" if dist[i][j]>=INF else str(dist[i][j]) for j in range(V)]))
	return 0

def target(*args):
	return entry_point, None

if __name__ == '__main__': entry_point([])

Submission status: Accepted

Solution code:
#!/usr/bin/python
import sys,heapq
try:
	import rpython.rlib.streamio
	stream=rpython.rlib.streamio.fdopen_as_stream(sys.stdin.fileno(),'r')
	raw_input=stream.readline
	def cmp_lt(x,y): return x < y
	heapq.cmp_lt=cmp_lt
	COMPILE=123456789012
	def compile(a,b,c):
		return ((a+COMPILE)<<18) | (b<<9) | c
	def decompile(a):
		return ((a>>18)-COMPILE,(a>>9)&511,a&511)
except ImportError:
	def compile(a,b,c):
		return (a,b,c)
	def decompile(a):
		return a
	if sys.version_info[0]>=3: raw_input=input

INF=1234567890123456789
def shortestPath(g,dist,prev):
	n = len(g)-1
	h = [INF]*n+[0]
	for k in range(n+1):
		for i in range(n+1):
			for e in g[i]:
				if h[e[1]]<INF and e[0]<INF and h[e[2]] > h[e[1]] + e[0]:
					h[e[2]] = h[e[1]] + e[0]
					if k==n: return False # negative cycle
	for i in range(n):
		for e in g[i]:
			e[0]+=h[i]-h[e[2]]
	for s in range(n):
		Q=[]
		heapq.heappush(Q,compile(0,s,s))
		while Q:
			e = decompile(heapq.heappop(Q))
			if prev[s][e[2]]!=-2: continue
			prev[s][e[2]] = e[1]
			for f in g[e[2]]:
				if e[0]<INF and f[0]<INF and dist[s][f[2]] > e[0] + f[0]:
					dist[s][f[2]] = e[0] + f[0]
					heapq.heappush(Q,compile(e[0]+f[0],f[1],f[2]))
		for u in range(n):
			if dist[s][u]<INF: dist[s][u] += h[u] - h[s]
	return True

def entry_point(argv):
	V,E=[int(e) for e in raw_input().rstrip().split(' ')]
	g=[[] for i in range(V+1)]
	dist=[[INF]*V for i in range(V)]
	prev=[[-2]*V for i in range(V)]
	for i in range(V): g[i].append([0,i,i])
	for i in range(V): g[V].append([0,V,i])
	for i in range(E):
		s,t,e=[int(e) for e in raw_input().rstrip().split(' ')]
		g[s].append([e,s,t])
	if not shortestPath(g,dist,prev):
		print("NEGATIVE CYCLE")
	else:
		for i in range(V):
			print(' '.join(["INF" if dist[i][j]>=INF else str(dist[i][j]) for j in range(V)]))
	return 0

def target(*args):
	return entry_point, None

if __name__ == '__main__': entry_point([])

Submission status: Accepted

Solution code:
INF = 1e12

v, e = (int(s) for s in input().split())
cost = [[INF] * v for i in range(v)]
for i in range(v):
    cost[i][i] = 0

for i in range(e):
    si, ti, di = (int(s) for s in input().split())
    cost[si][ti] = di

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

if any(cost[i][i] for i in range(v)):
    print('NEGATIVE CYCLE')
else:
    for di in cost:
        ldi = []
        for dij in di:
            if dij == INF:
                ldi.append('INF')
            else:
                ldi.append(str(dij))
        print(' '.join(ldi))

Submission status: Accepted

Solution code:
INF = 1e12

v, e = map(int, input().split())
cost = [[INF] * v for i in range(v)]
for i in range(v):
    cost[i][i] = 0

for i in range(e):
    si, ti, di = map(int, input().split())
    cost[si][ti] = di

for k in range(v):
    for i in range(v):
        for j in range(v):
            if cost[i][k] != INF and cost[k][j] != INF:
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

if any(cost[i][i] for i in range(v)):
    print('NEGATIVE CYCLE')
else:
    for di in cost:
        ldi = []
        for dij in di:
            if dij == INF:
                ldi.append('INF')
            else:
                ldi.append(str(dij))
        print(' '.join(ldi))

Submission status: Accepted

Solution code:
#!/usr/bin/python
import sys,heapq
try:
	import rpython.rlib.streamio
	stream=rpython.rlib.streamio.fdopen_as_stream(sys.stdin.fileno(),'r')
	raw_input=stream.readline
	def cmp_lt(x,y): return x < y
	heapq.cmp_lt=cmp_lt
	COMPILE=123456789012
	def compile(a,b,c):
		return ((a+COMPILE)<<18) | (b<<9) | c
	def decompile(a):
		return ((a>>18)-COMPILE,(a>>9)&511,a&511)
except ImportError:
	def compile(a,b,c):
		return (a,b,c)
	def decompile(a):
		return a
	if sys.version_info[0]>=3: raw_input=input

INF=1234567890123456789
def shortestPath(g,dist,prev):
	n = len(g)-1
	h = [INF]*n+[0]
	for k in range(n+1):
		for i in range(n+1):
			for e in g[i]:
				if h[e[1]]<INF and e[0]<INF and h[e[2]] > h[e[1]] + e[0]:
					h[e[2]] = h[e[1]] + e[0]
					if k==n: return False # negative cycle
	for i in range(n):
		for e in g[i]:
			e[0]+=h[i]-h[e[2]]
	for s in range(n):
		Q=[]
		heapq.heappush(Q,compile(0,s,s))
		while Q:
			e = decompile(heapq.heappop(Q))
			if prev[s][e[2]]!=-2: continue
			prev[s][e[2]] = e[1]
			for f in g[e[2]]:
				if e[0]<INF and f[0]<INF and dist[s][f[2]] > e[0] + f[0]:
					dist[s][f[2]] = e[0] + f[0]
					heapq.heappush(Q,compile(e[0]+f[0],f[1],f[2]))
		for u in range(n):
			if dist[s][u]<INF: dist[s][u] += h[u] - h[s]
	return True

def entry_point(argv):
	V,E=[int(e) for e in raw_input().rstrip().split(' ')]
	g=[[] for i in range(V+1)]
	dist=[[INF]*V for i in range(V)]
	prev=[[-2]*V for i in range(V)]
	for i in range(V): g[i].append([0,i,i])
	for i in range(V): g[V].append([0,V,i])
	for i in range(E):
		s,t,e=[int(e) for e in raw_input().rstrip().split(' ')]
		g[s].append([e,s,t])
	if not shortestPath(g,dist,prev):
		print("NEGATIVE CYCLE")
	else:
		for i in range(V):
			print(' '.join(["INF" if dist[i][j]>=INF else str(dist[i][j]) for j in range(V)]))
	return 0

def target(*args):
	return entry_point

if __name__ == '__main__': entry_point([])

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop


def floyd(dis, V):
    for i in range(V): dis[i][i] = 0
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dis[i][k] != sys.maxint and dis[k][j] != sys.maxint and dis[i][k] + dis[k][j] < dis[i][j]:
                    dis[i][j] = dis[i][k] + dis[k][j]
                    
    for i in range(V):
        if dis[i][i] < 0:
            return 'NEGATIVE CYCLE'
    return 'NO NEGATIVE CYCLE'
    
    
if __name__ == '__main__':
    line = sys.stdin.readline()
    V, E = line.split()
    V, E = int(V), int(E)
    dis = [[sys.maxint for j in range(V)] for i in range(V)]
    
    for i in range(E):
        line = sys.stdin.readline()
        a, b, w = line.split()
        a, b, w = int(a), int(b), int(w)
        dis[a][b] = w
        
        
    judge = floyd(dis, V)
    if judge == 'NEGATIVE CYCLE':
        sys.stdout.write(judge + '\n')
    else:
        for i in range(V):
            sys.stdout.write(' '.join(map(lambda x: str(x) if x < sys.maxint else 'INF', dis[i])) + '\n')

Submission status: Accepted

Solution code:
class exist_negative_cycle(Exception):
    pass
def warshall_floyd(g, size):
    d = [[float('inf')] * size for _ in range(size)]

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

    for u in g:
        for length, v in g[u]:
            d[u][v] = length

    for k in range(size):
        for i in range(size):
            for j in range(size):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    for i in range(size):
        if d[i][i] < 0:
            raise exist_negative_cycle
    return d


from collections import defaultdict
from sys import stdin
import math
readline = stdin.readline

v, e = map(int, readline().split())
g = defaultdict(list)
for i in range(e):
    s, t, length = map(int, readline().split())
    g[s].append((length, t))
try:
    d = warshall_floyd(g, v)
    for di in d:
        print(' '.join(['INF' if math.isinf(dij) else str(dij) for dij in di]))
except exist_negative_cycle:
    print('NEGATIVE CYCLE')

Submission status: Accepted

Solution code:
def warshall_floyd(graph, edges):
    N = len(graph)
    inf = Infinity()  # !_!
    for i in xrange(N):
        for j in xrange(N):
            if i == j:
                graph[i][j] = 0
            else:
                graph[i][j] = inf
    for e in edges:
        graph[e.source][e.destination] = e.weight
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                if inf in (graph[i][j], graph[i][k], graph[k][j]):  # !_!
                    continue
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    raise NegativeCycleError

def main():
    V, E = map(int, raw_input().split())
    graph = [[None] * V for _ in xrange(V)]
    edges = []
    for _ in xrange(E):
        s, t, d = map(int, raw_input().split())
        edges.append(Edge(s, t, d))
    try:
        warshall_floyd(graph, edges)
        for g in graph:
            print " ".join(map(str, g))
    except NegativeCycleError:
        print "NEGATIVE CYCLE"

class Infinity(object):
    def __eq__(self, other):
        return other is self

    def __lt__(self, other):
        return False

    def __gt__(self, other):
        return True

    def __add__(self, other):
        return self

    def __radd__(self, other):
        return self

    def __str__(self):
        return "INF"
    __repr__ = __str__

class NegativeCycleError(Exception):
    pass

class Edge(object):
    def __init__(self, source, destination, weight):
        self.source = source
        self.destination = destination
        self.weight = weight

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def warshall_floyd(graph, edges):
    N = len(graph)
    for i in xrange(N):
        for j in xrange(N):
            if i == j:
                graph[i][j] = 0
            else:
                graph[i][j] = Infinity()
    for e in edges:
        graph[e.source][e.destination] = e.weight
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    for i in xrange(N):
        if graph[i][i] < 0:
            raise NegativeCycleError

def main():
    V, E = map(int, raw_input().split())
    graph = [[None] * V for _ in xrange(V)]
    edges = []
    for _ in xrange(E):
        s, t, d = map(int, raw_input().split())
        edges.append(Edge(s, t, d))
    try:
        warshall_floyd(graph, edges)
        for g in graph:
            print " ".join(map(str, g))
    except NegativeCycleError:
        print "NEGATIVE CYCLE"

class Infinity(object):
    def __eq__(self, other):
        return other is self

    def __lt__(self, other):
        return False

    def __gt__(self, other):
        return True

    def __add__(self, other):
        return self

    def __radd__(self, other):
        return self

    def __str__(self):
        return "INF"
    __repr__ = __str__

class NegativeCycleError(Exception):
    pass

class Edge(object):
    def __init__(self, source, destination, weight):
        self.source = source
        self.destination = destination
        self.weight = weight

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop
from collections import Counter, defaultdict, deque, OrderedDict
from sys import setrecursionlimit as setreclim
from sys import maxsize
from bisect import bisect_left, bisect, insort_left, insort
from math import ceil, log, factorial, hypot, pi
from fractions import gcd
from copy import deepcopy
from functools import reduce
from operator import mul
from itertools import product, permutations, combinations, accumulate, cycle
from string import ascii_uppercase, ascii_lowercase, ascii_letters, digits, hexdigits, octdigits

prod = lambda l: reduce(mul, l)
prodmod = lambda l, mod: reduce(lambda x, y: mul(x,y)%mod, l)

class WarshallFloyd():
    """Warshall-Floyd Algorithm: 
       find the lengths of the shortest paths between all pairs of vertices
    """

    def __init__(self, V, E, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list
            start: start vertex
            INF: Infinity distance
        """
        self.V = V
        self.E = E
        self.warshall_floyd(INF)

    def warshall_floyd(self, INF):
        self.distance = [[INF] * self.V for _ in range(V)]
        for i in range(V): self.distance[i][i] = 0
        for fr in range(V):
            for to, cost in self.E[fr]:
                self.distance[fr][to] = cost
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    if self.distance[i][k] != INF and self.distance[k][j] != INF:
                        self.distance[i][j] = min(self.distance[i][j], self.distance[i][k] + self.distance[k][j])

    def hasNegativeCycle(self):
        for i in range(V):
            if self.distance[i][i] < 0:
                return True
        else:
            return False
                
V, E = map(int, input().split())
INF = 10**10
edge = [[] for _ in range(V)]

for i in range(E):
    s, t, cost = map(int, input().split())
    edge[s].append((t, cost))

allsp = WarshallFloyd(V, edge, INF)
            
if allsp.hasNegativeCycle():
    print('NEGATIVE CYCLE')
else:
    for dist in allsp.distance:
        print(*[d if d != INF else 'INF' for d in dist])

Submission status: Accepted

Solution code:
V, E = map(int, raw_input().split())
G = [[float("inf")] * V for i in xrange(V)]
for i in xrange(V):
    G[i][i] = 0
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    G[s][t] = d

for k in xrange(V):
    for i in xrange(V):
        for j in xrange(V):
            G[i][j] = min(G[i][j], G[i][k] + G[k][j])

for i in xrange(V):
    if G[i][i] < 0:
        print "NEGATIVE CYCLE"
        exit()
    for j in xrange(V):
        if G[i][j] == float("inf"):
            G[i][j] = "INF"

for line in G:
    print " ".join(map(str, line))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from math import isinf


def main():
    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][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")
            return

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

main()

Submission status: Accepted

Solution code:
from __future__ import division
from collections import defaultdict, deque
from heapq import heappush, heappop
from sys import stdin

class UnionFindSet:
	def __init__(self, nodes):
		self.fa = {}
		for n in nodes:
			self.fa[n] = n

	def find(self, x):
		if self.fa[x] == x:
			return x
		else:
			self.fa[x] = self.find(self.fa[x])
			return self.fa[x]

	def union(self, x, y):
		fx = self.find(x)
		fy = self.find(y)
		if fx == fy:
			return fx
		else:
			self.fa[fx] = fy
			return fy


"""
graph is a hash
graph["nodes"] is a list of all nodes in the graph
graph["edges"] is a list of all edges in the graph in (x, y, w) form
  - x is the first nodes
  - y is the second nodes
  - w is the weight of the edges
graph["relation"] is the graph relation of the graph
"""

def kruscal(graph):
	"kruscal minimum spanning tree algorithm"
	ufset = UnionFindSet(graph["nodes"])

	ret = 0

	for (x, y, w) in sorted(graph["edges"], key = lambda x: x[-1]):
		fx = ufset.find(x)
		fy = ufset.find(y)
		if fx != fy:
			ret += w
			ufset.union(fx, fy)
		else:
			pass
	return ret


def dijkstra(graph, root):
	"dijkstra algorithm for single source shortest algorithm"
	dis, vis = {}, {}
	for n in graph["nodes"]:
		dis[n] = 10 ** 9
		vis[n] = False

	heap = []
	dis[root] = 0
	heappush(heap, (0, root))

	while heap:
		_, n = heappop(heap)
		vis[n] = True
		for (y, w) in graph["adj"][n]:
			if not vis[y] and dis[n] + w < dis[y]:
				dis[y] = dis[n] + w
				heappush(heap, (dis[y], y))

	return dis

def belmanFord(graph, root):
	"belman ford algorithm for graph with negative edges"
	dis = {}
	for n in graph["nodes"]:
		dis[n] = 10 ** 9

	dis[root] = 0

	# update for n - 1 times
	for _ in range(len(graph["nodes"]) - 1):
		for (x, y, w) in graph["edges"]:
			if dis[x] + w < dis[y]:
				dis[y] = dis[x] + w

	# try to find the component which can be reached by the source
	connect = set([root])
	que = deque([root])

	while que:
		n = que.popleft()
		for (y, _) in graph["adj"][n]:
			if not y in connect:
				connect.add(y)
				que.append(y)

	dis["negcicle"] = False
	for (x, y, w) in graph["edges"]:
		if dis[x] + w < dis[y] and x in connect:
			dis["negcicle"] = True

	dis["con"] = connect
	return dis

def floyd(graph):
	n = len(graph["nodes"])
	dis = [[10 ** 20 for _ in range(n)] for _ in range(n)]
	for i in range(n): dis[i][i] = 0

	for x in graph["nodes"]:
		for (y, w) in graph["adj"][x]:
			dis[x][y] = w


	for k in range(n):
		for i in range(n):
			for j in range(n):
				if dis[i][k] < 10 ** 20 and dis[k][j] < 10 ** 20:
					dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

	return dis


if __name__ == '__main__':
	V, E= map(int, stdin.readline().strip().split())
	graph = {}
	graph["nodes"] = [i for i in range(V)]
	graph["edges"] = []
	graph["adj"] = defaultdict(list)
	for _ in range(E):
		x, y, w = map(int, stdin.readline().strip().split())
		graph["edges"].append((x, y, w))
		graph["adj"][x].append((y, w))

	dis = floyd(graph)

	negcycle = False

	for i in range(len(graph["nodes"])):
		if dis[i][i] < 0:
			negcycle = True

	if negcycle:
		print "NEGATIVE CYCLE"
	else:
		for row in dis:
			print ' '.join(map(lambda x: str(x) if x < 10 ** 20 else "INF", row))

Submission status: Accepted

Solution code:
from __future__ import division
from collections import defaultdict, deque
from heapq import heappush, heappop
from sys import stdin


def floyd(graph):
    n = len(graph["nodes"])
    dis = [[10 ** 20 for _ in range(n)] for _ in range(n)]
    for i in range(n): dis[i][i] = 0

    for x in graph["nodes"]:
        for (y, w) in graph["adj"][x]:
            dis[x][y] = w


    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dis[i][k] < 10 ** 20 and dis[k][j] < 10 ** 20:
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    return dis


if __name__ == '__main__':
    V, E= map(int, stdin.readline().strip().split())
    graph = {}
    graph["nodes"] = [i for i in range(V)]
    graph["edges"] = []
    graph["adj"] = defaultdict(list)
    for _ in range(E):
        x, y, w = map(int, stdin.readline().strip().split())
        graph["edges"].append((x, y, w))
        graph["adj"][x].append((y, w))

    dis = floyd(graph)

    negcycle = False

    for i in range(len(graph["nodes"])):
        if dis[i][i] < 0:
            negcycle = True

    if negcycle:
        print "NEGATIVE CYCLE"
    else:
        for row in dis:
            print ' '.join(map(lambda x: str(x) if x < 10 ** 20 else "INF", row))

Submission status: Accepted

Solution code:
INF = 1<<31
V, E = map(int, raw_input().split())
l = [[INF]*V for i in range(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    l[s][t] = d
for k in range(V):
    for i in range(V):
        for j in range(V):
            if l[i][k] != INF and l[k][j] != INF:
                l[i][j] = min(l[i][j], l[i][k] + l[k][j])
for i in range(V):
    if l[i][i] < 0:
        print "NEGATIVE CYCLE"
        break
    l[i][i] = 0
else:
    for r in l:
        for i in range(V):
            if r[i] == INF: r[i] = "INF"
        print " ".join(map(str, r))

Submission status: Accepted

Solution code:
INF = float("inf")
V, E = map(int, raw_input().split())
l = [[INF]*V for i in range(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    l[s][t] = d
for k in range(V):
    for i in range(V):
        for j in range(V):
            l[i][j] = min(l[i][j], l[i][k] + l[k][j])
for i in range(V):
    if l[i][i] < 0:
        print "NEGATIVE CYCLE"
        break
    l[i][i] = 0
else:
    for r in l:
        for i in range(V):
            if r[i] == INF: r[i] = "INF"
        print " ".join(map(str, r))

Submission status: Accepted

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

negative_cycle = False

for k in range(V):
    for i in range(V):
        for j in range(V):
            if dist[i][k] == float('inf') or dist[k][j] == float('inf'):
                continue
            if 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:
        negative_cycle = True

if negative_cycle:
    print('NEGATIVE CYCLE')
else:
    for i in range(V):
        d = ['INF' if e == float('inf') else e for e in  dist[i]]
        print(*d)

Submission status: Accepted

Solution code:
nv, ne = map(int, input().split())

costs = [[None] * nv for _ in range(nv)]
for i in range(nv):
    costs[i][i] = 0

while ne:
    s, t, d = map(int, input().split())
    costs[s][t] = d
    ne -= 1


def loop():
    for k in range(nv):
        for i in range(nv):
            for j in range(nv):
                if costs[i][k] is None or costs[k][j] is None:
                    continue
                tmp_cost = costs[i][k] + costs[k][j]
                if i == j and tmp_cost < 0:
                    print('NEGATIVE CYCLE')
                    return False
                if costs[i][j] is None or costs[i][j] > tmp_cost:
                    costs[i][j] = tmp_cost
    return True


if loop():
    for vc in costs:
        print(*('INF' if c is None else c for c in vc))

Submission status: Accepted

Solution code:
v,e=map(int,raw_input().split())
glist=[[float('inf')]*v for i in xrange(v)]
A=[[0]*v for i in xrange(v)]
negativect=0
for i in xrange(e):
    s,t,d=map(int,raw_input().split())
    glist[s][t]=d
for i in xrange(v):
    for j in xrange(v):
        if i==j:
            A[i][j]=0
        else:
            A[i][j]=glist[i][j]
for k in xrange(v):
    for i in xrange(v):
        for j in xrange(v):
            A[i][j]=min(A[i][j],A[i][k]+A[k][j])
for i in xrange(v):
    for j in xrange(v):
        if A[i][j]==float('inf'):
            A[i][j]='INF'
        if i==j and A[i][j]<0:
            negativect+=1
        A[i][j]=str(A[i][j])
if negativect>0:
    print('NEGATIVE CYCLE')
else:
    for i in xrange(v):
        print(" ".join(A[i]))

Submission status: Accepted

Solution code:
INF = 10**18

V, E = map(int, raw_input().split())
cost = [[INF]*V for i in xrange(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    cost[s][t] = d
for i in xrange(V):
    cost[i][i] = 0

for k in xrange(V):
    for i in xrange(V):
        for j in xrange(V):
            if cost[i][k]!=INF and cost[k][j]!=INF:
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
if any(cost[i][i]<0 for i in xrange(V)):
    print "NEGATIVE CYCLE"
else:
    print "\n".join(" ".join(map(lambda e: str(e) if e<INF else "INF", e)) for e in cost)

Submission status: Accepted

Solution code:
def print_solve(ans):
    if "negative" in ans:
        print("NEGATIVE CYCLE")
    else:
        for l in ans:
            for c in l[:-1]:
                if c == float("inf"):
                    print("INF",end=" ")
                else:
                    print(c,end=" ")
            if l[-1] == float("inf"):
                print("INF")
            else:
                print(l[-1])

def solve(graph_data, num_v):
    ans = []

    for i in range(num_v):
        ans.append(partial_solve(graph_data, i, num_v))

    return ans

def partial_solve(graph_data, source, num_v):
    ans = [0 if i == source else float('inf') for i in range(num_v)]

    i = 0
    while (ans != solver_iteration(graph_data, ans)):
        ans = solver_iteration(graph_data, ans)
        i += 1
        if i >= num_v:
            return "negative"

    return ans

def solver_iteration(graph_data, prev_ans):
    new_ans = prev_ans[0:]

    for i, v in enumerate(new_ans):
        if v == float('inf') or i not in graph_data:
            continue

        for t, w in graph_data[i]:
                new_ans[t] = min(new_ans[t], v + w)

    return new_ans

def main():
    l = input().split()
    V = int(l[0])
    E = int(l[1])

    graph = {}
    for i in range(E):
        l = input().split()
        s = int(l[0])
        t = int(l[1])
        d = int(l[2])

        if s in graph:
            graph[s].append((t,d))
        else:
            graph[s] = [(t,d)]

    print_solve(solve(graph, V))

if __name__ == "__main__":
    main()