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: Wrong Answer

Solution code:
from sys import stdin
from collections import deque

def read_graph(v, e):
    A = [ [float('inf')]*v for _ in range(v) ]
    for i in range(v):
        A[i][i] = 0
    for _ in range(e):
        line = list(stdin.readline().strip().split())
        i = line[0]
        j = line[1]
        k = line[2]
        A[int(i)][int(j)] = int(k)
    return A

def worshall_floyd(A, v):
    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])
    return A

def print_ans(A):
    if min(min(A)) < 0:
        print('NEGATIVE CYCLE')
    else:
        for i in A:
            print(*[str(k).upper() for k in i], sep=' ')

v, e = [int(i) for i in input().split()]
A = read_graph(v, e)
print_ans(worshall_floyd(A, v))

Submission status: Wrong Answer

Solution code:
from sys import exit
INF = 1<<21
V,E = [int(n) for n in input().split()]
s = [0]*E
t = [0]*E
d = [0]*E
dist = [[INF for _ in range(V)] for __ in range(V)]
for i in range(V):
    dist[i][i]= 0
for i in range(E):
    s[i], t[i], d[i] = [int(n) for n in input().split()]
    dist[s[i]][t[i]] = d[i]

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

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

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

# N = int(input())
# a = [int(input()) for _ in range(N)]
# S = str(input())
# L = len(S)
# T = str(input())
# exit()

Submission status: Wrong Answer

Solution code:
import copy

INF = 10**10
v, e = map(int, input().split())
M = [[INF]*v for i in range(v)]
for i in range(v):
    M[i][i] = 0
for i in range(e):
    s, t, d = map(int, input().split())
    M[s][t] = d

# k:グラフの範囲
ans = copy.deepcopy(M)
for k in range(v):
    for i in range(v):
        for j in range(v):
            # i, jのグラフの最短距離
            if k == 0:
                ans[i][j] = M[i][j]
            else:
                ans[i][j] = min(ans[i][j], ans[i][k]+ans[k][j])

flag = False
for line in ans:
    if any([i < 0 for i in line]):
        flag = True
        break
    else:
        line = ['INF' if tmp == INF else tmp for tmp in line]
if flag:
    print('NEGATIVE CYCLE')
else:
    print(*line)

Submission status: Wrong Answer

Solution code:
import copy

INF = 10**10
v, e = map(int, input().split())
M = [[INF]*v for i in range(v)]
for i in range(v):
    M[i][i] = 0
for i in range(e):
    s, t, d = map(int, input().split())
    M[s][t] = d

# k:グラフの範囲
ans = copy.deepcopy(M)
for k in range(v):
    for i in range(v):
        for j in range(v):
            # i, jのグラフの最短距離
            if k == 0:
                ans[i][j] = M[i][j]
            else:
                ans[i][j] = min(ans[i][j], ans[i][k]+ans[k][j])

flag = False
for line in ans:
    if any([i < 0 for i in line]):
        flag = True
        break
if flag:
    print('NEGATIVE CYCLE')
else:
    for line in ans:
        line = ['INF' if tmp == INF else tmp for tmp in line]
        print(*line)

Submission status: Wrong Answer

Solution code:
import copy

INF = 10**10
v, e = map(int, input().split())
M = [[INF]*v for i in range(v)]
for i in range(v):
    M[i][i] = 0
for i in range(e):
    s, t, d = map(int, input().split())
    M[s][t] = d

# k:グラフの範囲
ans = copy.deepcopy(M)
for k in range(v):
    for i in range(v):
        for j in range(v):
            # i, jのグラフの最短距離
            if k == 0:
                ans[i][j] = M[i][j]
            else:
                ans[i][j] = min(ans[i][j], ans[i][k]+ans[k][j])

flag = False
for i in range(v):
    if ans[i][i] < 0:
        flag = True
        break
if flag:
    print('NEGATIVE CYCLE')
else:
    for line in ans:
        line = ['INF' if tmp == INF else tmp for tmp in line]
        print(*line)

Submission status: Wrong Answer

Solution code:
import copy

INF = 10**10
v, e = map(int, input().split())
M = [[INF]*v for i in range(v)]
for i in range(v):
    M[i][i] = 0
for i in range(e):
    s, t, d = map(int, input().split())
    M[s][t] = d

# k:グラフの範囲
ans = copy.deepcopy(M)
for k in range(v):
    for i in range(v):
        if M[i][k] == INF:
            continue
        for j in range(v):
            if M[k][j] == INF:
                continue
            # i, jのグラフの最短距離
            ans[i][j] = min(ans[i][j], ans[i][k]+ans[k][j])

flag = False
for i in range(v):
    if ans[i][i] < 0:
        flag = True
        break
if flag:
    print('NEGATIVE CYCLE')
else:
    for line in ans:
        line = ['INF' if tmp == INF else tmp for tmp in line]
        print(*line)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from copy import deepcopy

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

# ワーシャルフロイド(頂点数, 隣接行列(0-indexed))
def warshall_floyd(N: int, graph: list) -> list:
    res = deepcopy(graph)
    for i in range(N):
        # 始点 = 終点、は予め距離0にしておく
        res[i][i] = 0
    # 全頂点の最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                res[i][j] = min(res[i][j], res[i][k] + res[k][j])
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for i in range(N):
        if res[i][i] < 0:
            return []
    return res

N,M=MAP()
G=[[INF]*N for i in range(N)]
for i in range(M):
    s,t,d=MAP()
    G[s][t]=d

ans=warshall_floyd(N, G)

if not len(ans):
    print('NEGATIVE CYCLE')
    exit()
for i in range(N):
    print(*ans[i])

Submission status: Wrong Answer

Solution code:
INF = 1000000000

def BellmanFord(s, v, edge):
    dp = [INF] * v
    dp[s] = 0
    for i in range(0, v):
        for fr, to, d in edge:
            if dp[to] > dp[fr] + d:
                dp[to] = dp[fr] + d
                if i == v - 1:
                    return -1
    return dp

edge = []
dp = []
line = input()
v, e = list(map(int, line.split()))
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, line.split()))
    edge += [[s, t, d]]
for s in range(0, v):
    dp = BellmanFord(s, v, edge)
    if dp == -1:
        print("NEGATIVE CYCLE")
        break
    else:
        print(" ".join(map(str, [dp[t] if dp[t] != INF else "INF" for t in range(0, v)])))

Submission status: Wrong Answer

Solution code:
INF = 1000000000

def BellmanFord(s, v, graph):
    dp = [INF] * v
    dp[s] = 0
    for i in range(0, v):
        for k in range(0, v):
            dp1 = [dp[k] + graph[k][j] if dp[k] != INF and graph[k][j] != 0 and dp[j] > dp[k] + graph[k][j]
                  else dp[j]
                  for j in range(0, v) ]
            if dp1 != dp and i == v - 1:
                return -1
            dp = dp1
    return dp

dp = []
line = input()
v, e = list(map(int, line.split()))
graph = [ [0] * v for _ in range(0, v)]
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, line.split()))
    graph[s][t] = d
for s in range(0, v):
    dp = BellmanFord(s, v, graph)
    if dp == -1:
        print("NEGATIVE CYCLE")
        break
    else:
        print(" ".join(map(str, [dp[t] if dp[t] != INF else "INF" for t in range(0, v)])))

Submission status: Wrong Answer

Solution code:
INF = 1000000000

def BellmanFord_edge(s, v, edge):
    dp = [INF] * v
    dp[s] = 0
    for i in range(0, v):
        dp1 = dp[:]
        for fr, to, d in edge:
            if dp[fr] == INF:
                continue
            if dp[to] > dp[fr] + d:
                dp[to] = dp[fr] + d
                if i == v - 1:
                    return -1
        if dp == dp1:
            break
    return dp

def BellmanFord_graph(s, v, graph):
    dp = [INF] * v
    dp[s] = 0
    for i in range(0, v):
        for k in range(0, v):
            dp1 = [dp[k] + graph[k][j] if dp[k] != INF and graph[k][j] != INF and dp[j] > dp[k] + graph[k][j]
                  else dp[j]
                  for j in range(0, v) ]
            if dp1 != dp and i == v - 1:
                return -1
            dp = dp1
    return dp

dp = []
line = input()
v, e = list(map(int, line.split()))
graph = [ [INF] * v for _ in range(0, v)]
edge = []
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, line.split()))
    edge += [[s, t, d]]
    graph[s][t] = d
for s in range(0, v):
#    dp = BellmanFord(s, v, graph)
    dp = BellmanFord_edge(s, v, edge)
    if dp == -1:
        print("NEGATIVE CYCLE")
        break
    else:
        print(" ".join(map(str, [dp[t] if dp[t] != INF else "INF" for t in range(0, v)])))

Submission status: Wrong Answer

Solution code:
import sys

inf = int(1e12)

def shortestPath(graph):
    n = len(graph)
    dist = [[inf for _ in range(n)] for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    
    for v in range(n):
        for u, cost in graph[v]:
            dist[v][u] = cost

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

def main():
    v, e = map(int, input().split())
    
    graph = [[] for _ in range(v)]
    
    for i in range(e):
        a, b, cost = map(int, input().split())
        graph[a].append((b, cost))
            
    dist_mat = shortestPath(graph)

    for i in range(v):
        output = []
        for j in range(v):
            if dist_mat[i][j] >= inf:
                output.append("INF")
            else:
                output.append(str(dist_mat[i][j]))
        print(" ".join(output))

main()

Submission status: Wrong Answer

Solution code:
import sys

inf = int(1e12)

def shortestPath(graph):
    n = len(graph)
    dist = [[inf for _ in range(n)] for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    
    for v in range(n):
        for u, cost in graph[v]:
            dist[v][u] = cost

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

def main():
    v, e = map(int, input().split())
    
    graph = [[] for _ in range(v)]
    
    for i in range(e):
        a, b, cost = map(int, input().split())
        graph[a].append((b, cost))
            
    dist_mat = shortestPath(graph)

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

    for i in range(v):
        output = []
        for j in range(v):
            if dist_mat[i][j] >= inf:
                output.append("INF")
            else:
                output.append(str(dist_mat[i][j]))
        print(" ".join(output))

main()

Submission status: Wrong Answer

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: Wrong Answer

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] + 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: Wrong Answer

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):
                    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: Wrong Answer

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):
    for j in xrange(V):
        if G[i][j] < 0:
            print "NEGATIVE CYCLE"
            exit()
        if G[i][j] == float("inf"):
            G[i][j] = "INF"

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

Submission status: Wrong Answer

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 ** 9 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):
				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: "INF" if x == 10 ** 9 else str(x), row))

Submission status: Wrong Answer

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 ** 9 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 ** 9 and dis[k][j] < 10 ** 9:
					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 ** 9 else "INF", row))

Submission status: Wrong Answer

Solution code:
INF = (1<<31)-1
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: Wrong Answer

Solution code:
V, E = map(int, input().split())
visited = [False] * V
nodes = [[] for i in range(V)]
cost = [[] for i in range(V)]
for i in range(E):
    s, t, d = map(int, input().split())
    nodes[s].append(t)
    cost[s].append(d)

dist = [[float('inf') for j in range(V)] for i in range(V)]
for i in range(V):
    dist[i][i] = 0

negative_cycle = False

for k in range(V):
    for i in range(V):
        for j in range(len(nodes[i])):
            if dist[k][nodes[i][j]] > dist[k][i] + cost[i][j]:
                dist[k][nodes[i][j]] = dist[k][i] + cost[i][j]
                # if k == V - 1:
                #     dist[nodes[i][j]] = -float('inf')
                #     negative_cycle = True
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)
        # if dist[i] == float('inf'):
        #     print('INF')
        # else:
        #     print(dist[i])

Submission status: Wrong Answer

Solution code:
V, E = map(int, input().split())
visited = [False] * V
nodes = [[] for i in range(V)]
cost = [[] for i in range(V)]
for i in range(E):
    s, t, d = map(int, input().split())
    nodes[s].append(t)
    cost[s].append(d)

dist = [[float('inf') for j in range(V)] for i in range(V)]
for i in range(V):
    dist[i][i] = 0

negative_cycle = False

for k in range(V):
    for i in range(V):
        for j in range(len(nodes[i])):
            if dist[k][i] == float('inf'):
                continue
            if dist[k][nodes[i][j]] > dist[k][i] + cost[i][j]:
                dist[k][nodes[i][j]] = dist[k][i] + cost[i][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: Wrong Answer

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

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 costs[i][j] is None or costs[i][j] > tmp_cost:
                costs[i][j] = tmp_cost

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

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
import heapq

def solve(num_v ,graph_data): # dict -> [[arr]]
    solution = []
    for i in range(num_v):
        solution.append(partial_solve(i, num_v, graph_data))
    return solution

def partial_solve(source, num_v,graph_data):
    heap = [(0,source)]
    partial_solution = [float("inf") for _ in range(num_v)]
    while heap:
        dist, target = heapq.heappop(heap)
        if partial_solution[target] > dist:
            if partial_solution[target] != float("inf"):
                return ["negative"]
            partial_solution[target] = dist
            if target in graph_data:
                for edge in graph_data[target]:
                    heapq.heappush(heap, (dist+edge[1], edge[0]))
    return partial_solution

def print_solution(solution):
    if ["negative"] in solution:
        print("NEGATIVE CYCLE")
    else:
        print_matrix(solution)

def print_matrix(solution):
    for r in solution:
        l = ""
        for c in r:
            l += str_cell(c) + " "
        print(l[:-1])

def str_cell(cell):
    if cell == float("inf"):
        return "INF"
    else:
        return str(cell)

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

    graph = {}
    for i in range(E):
        l = input().split()
        source = int(l[0])
        target = int(l[1])
        dist = int(l[2])
        if source in graph:
            graph[source].append((target, dist))
        else:
            graph[source] = [(target, dist)]

    print_solution(solve(V, graph))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def print_solve(ans):
    if "negative" in ans:
        print("NEGATIVE CYCLE")
    else:
        for l in ans:
            for c in l[:-1]:
                print(c,end=" ")
            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'):
            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()