Problem:


All Pairs Shortest Path

Input

An edge-weighted graph G (V, E).

|V| |E|
s0 t0 d0
s1 t1 d1
:
s|E|-1 t|E|-1 d|E|-1

|V| is the number of vertices and |E| is the number of edges in G. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti  represent source and target vertices of i-th edge (directed) and di represents the cost of the i-th edge.

Output

If the graph contains a negative cycle (a cycle whose sum of edge costs is a negative value), print 

NEGATIVE CYCLE

in a line.

Otherwise, print

D0,0 D0,1 ... D0,|V|-1
D1,0 D1,1 ... D1,|V|-1
:
D|V|-1,0 D1,1 ... D|V|-1,|V|-1

The output consists of |V| lines. For each ith line, print the cost of the shortest path from vertex i to each vertex j (j = 0, 1, ... |V|-1) respectively. If there is no path from vertex i to vertex j, print "INF". Print a space between the costs.

Constraints

 1 ≤ |V| ≤ 100

 0 ≤ |E| ≤ 9900

 -2 &times 107 ≤ di ≤ 2 &times 107

 There are no parallel edges

 There are no self-loops

Sample Input 1

4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 7

Sample Output 1

0 1 3 4
INF 0 2 3
INF INF 0 1
INF INF 7 0

Sample Input 2

4 6
0 1 1
0 2 -5
1 2 2
1 3 4
2 3 1
3 2 7

Sample Output 2

0 1 -5 -4
INF 0 2 3
INF INF 0 1
INF INF 7 0

Sample Input 3

4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 -7

Sample Output 3

NEGATIVE CYCLE



Sample input:
4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 7


Sample output:
0 1 3 4
INF 0 2 3
INF INF 0 1
INF INF 7 0

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
n,e = [int(i) for i in input().split()]

"""隣接行列の初期化"""
INF = float("inf")
dist = [[float("inf")]*n for _ in [0]*n]
for i in range(n):
    dist[i][i] = 0

for _ in range(e):
    s,t,d = [int(i) for i in input().split()]
    dist[s][t] = d

def Floyd_Warshall(dist): # 
    """
    Floyd_Warshall 
    dist: 隣接行列（破壊される)
    #隣接行列のつながっていない辺はfloat("inf")で埋める（負辺を気にせずによい）
    #実行時間が気になるときは INF = 10**18 などで埋める（負辺に注意）
    #dist[i[i] < 0なる i があればnegative cycle
    """
    num_of_vertices = len(dist)
    for k in range(num_of_vertices):
        for i, c2 in enumerate(dj[k] for dj in dist):
            for j, (c1, c3) in enumerate(zip(dist[i], dist[k])):
                if c1 > c2+c3:
                    dist[i][j] = c2+c3

Floyd_Warshall(dist)

def has_negative_cycle(dist) -> bool:
    return any(row[i] < 0 for i, row in enumerate(dist))
 
if has_negative_cycle(dist):
    print("NEGATIVE CYCLE")
    exit()
else:
    for row in dist:
        print(" ".join(map(lambda n: str(n) if n!=INF else "INF", row)))

Submission status: Accepted

Solution code:
v, e = map(int, input().split())
inf = 2**32
dp = [[inf for _ in range(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())
    dp[s][t] = d

for k in range(v):
    for i in range(v):
        if dp[i][k] >= inf:
            continue
        for j in range(v):
            if dp[k][j] >= inf:
                continue
            dp[i][j] = min([dp[i][j], dp[i][k]+dp[k][j]])

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

if negative:
    print("NEGATIVE CYCLE")
else:
    for i in range(v):
        ans = []
        for j in range(v):
            if dp[i][j] >= inf:
                ans.append("INF")
            else:
                ans.append(str(dp[i][j]))
        print(" ".join(ans))

Submission status: Accepted

Solution code:
import sys
from math import isinf
def warshall_floyd(v_count: int):
    """ ワーシャルフロイド　(user:htkb)
    :param v_count: 頂点数
    :param matrix:  隣接行列(到達不能はfloat("inf"))
    """
    # 到達不能をfloat("inf")にしておけば余計なチェックを入れなくても
    # inf > inf+(-1) のような到達不能＋負辺が繋がってしまうことはない
    global matrix
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3 # min(c1, c2+c3)

if __name__ == "__main__":
    V,E = map(int, input().split())
    matrix = [[float('inf')]*V for _ in range(V)]
    for i in range(V):
        matrix[i][i] = 0

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

    warshall_floyd(V)
    for i in range(V):
        if matrix[i][i] < 0:
            print("NEGATIVE CYCLE")
            sys.exit()
    for mi in matrix:
        print(' '.join( ('INF' if isinf(dij) else str(dij) for dij in mi)))

Submission status: Accepted

Solution code:
INF = 2e10


def main():
    n, m = map(int, input().split())

    mat = [[INF] * n for i in range(n)]
    for i in range(n):
        mat[i][i] = 0
    for i in range(m):
        s, t, c = map(int, input().split())
        mat[s][t] = c

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

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

    for i in range(n):
        for j in range(n):
            if j > 0:
                print(' ', end="")
            if mat[i][j] == INF:
                print('INF', end="")
            else:
                print(mat[i][j], end="")
        print()


main()

Submission status: Accepted

Solution code:
V,E = map(int,input().strip().split())
K = [["INF" for _ in range(V)] for _ in range(V)]
for i in range(V):
    K[i][i] = 0
for t in range(E):
    S,T,D = map(int,input().strip().split())
    K[S][T] = D
for k in range(V):
    for i in range(V):
        for j in range(V):
            if (K[i][k] != "INF") and (K[k][j] != "INF"):
                if K[i][j] == "INF" or K[i][j] > K[i][k] + K[k][j]:
                    K[i][j] = K[i][k] + K[k][j]
b = 0
for t in range(V):
    if K[t][t] != "INF" and K[t][t] < 0:
        print("NEGATIVE CYCLE")
        b += 1
        break
if b == 0:
    for i in range(V):
        print(" ".join(map(str,K[i])))

Submission status: Accepted

Solution code:
def func(V, W):
    for k in range(V):
        for i in range(V):
            w_ik = W[i][k]
            for j, (w_ij, w_kj) in enumerate(zip(W[i], W[k])):
                W[i][j] = min(w_ij, w_ik + w_kj)

V, E = map(int, input().split())
W = [[float("inf")] * V for _ in range(V)]

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

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

func(V, W)

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

for temp in W:
    print(" ".join(list(map(str, temp))).upper())

Submission status: Accepted

Solution code:
INF = 2000000000


def read_adj_mat():
    nv, ne = [int(x) for x in input().split()]
    A = [[0 if fr == to else INF for fr in range(nv)] for to in range(nv)]
    for _ in range(ne):
        s, t, d = [int(x) for x in input().split()]
        A[s][t] = d
    return A


def get_shortest_paths(D):
    n = len(D)
    for to in range(n):
        for fr in range(n):
            here = D[fr][to]
            if here == INF:
                continue
            for to2 in range(n):
                here2 = D[to][to2]
                if here2 == INF:
                    continue
                D[fr][to2] = min(D[fr][to2], here + here2)


def print_result(D):
    for fr in range(len(D)):
        for to in range(len(D)):
            if to != 0:
                print(" ", end="")
            if D[fr][to] == INF:
                print("INF", end="")
            else:
                print(D[fr][to], end="")
        print()


def main():
    D = read_adj_mat()
    get_shortest_paths(D)
    for d in [D[x][x] for x in range(len(D))]:
        if d < 0:
            print("NEGATIVE CYCLE")
            break
    else:
        print_result(D)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
writelines = sys.stdout.writelines
write = sys.stdout.write

from collections import deque
from heapq import heappush, heappop

INF = 10**30
def Johnson(G):
    h = [0]*N

    update = 1
    for i in range(N):
        update = 0
        for v in range(N):
            d = h[v]
            for w, c in G[v]:
                if c + d < h[w]:
                    h[w] = d + c
                    update = 1
        if not update:
            break
    else:
        return None

    for v in range(N):
        d = h[v]
        g = G[v]
        for j, (w, c) in enumerate(g):
            g[j] = (w, c + d - h[w])

    D = []
    for i in range(N):
        dst = [INF]*N
        dst[i] = 0
        que = [(0, i)]
        while que:
            cost, v = heappop(que)
            if dst[v] < cost:
                continue
            for w, c in G[v]:
                if cost + c < dst[w]:
                    dst[w] = r = cost + c
                    heappush(que, (r, w))
        v = h[i]
        for j in range(N):
            if dst[j] == INF:
                dst[j] = INF
            else:
                dst[j] -= v - h[j]
        D.append(dst)

    return D


N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    s, t, d = map(int, input().split())
    G[s].append((t, d))

D = Johnson(G)
if D:
    ans = []
    for i in range(N):
        ans.append(" ".join(str(v) if v < INF else "INF" for v in D[i]))
        ans.append("\n")
    writelines(ans)
else:
    write("NEGATIVE CYCLE\n")

Submission status: Accepted

Solution code:
def input(f):
    global v, e, s, t, d
     
    v, e = map(int, f.readline().split())
    s = []
    t = []
    d = []
    for _ in range(e):
        s_, t_, d_ = map(int, f.readline().split())
        s.append(s_)
        t.append(t_)
        d.append(d_)
 
import os
 
if os.environ.get('ZEPPELIN_HOME'):
    import networkx as nx
    import matplotlib.pyplot as plt
     
    def visualize():
        G = nx.MultiDiGraph()
        for i in range(v):
            G.add_node(i, node_color='b')
        for i in range(e):
            G.add_edge(s[i], t[i], t=d[i])
 
        plt.figure()
        plt.style.use('seaborn')
        plt.axis("off")
        pos = nx.spring_layout(G)
        nodes = nx.draw_networkx_nodes(G, pos, node_color='w', linewidths=2)
        nodes.set_edgecolor('black')
        nx.draw_networkx_labels(G, pos)
        nx.draw_networkx_edges(G, pos)
 
        edge_labels = dict([((a, b), c['t']) for a, b, c in G.edges(data=True)])
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, label_pos=0.25, font_size=16)
 
        plt.show()
 
if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input1') as f:
        print('Example #1')
        input(f)
        visualize()
 
if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input2') as f:
        print('Example #2')
        input(f)
        visualize()
 
if os.environ.get('ZEPPELIN_HOME'):
    with open('/tmp/input3') as f:
        print('Example #3')
        input(f)
        visualize()
 
import sys
 
 
def init():
    global inf, g
    inf = sys.maxsize
     
    g = [[inf for _ in range(v)] for _ in range(v)]
    for i in range(v):
        g[i][i] = 0
    for i in range(e):
        g[s[i]][t[i]] = d[i]
         
 
def solve():
    init()
     
    for k in range(v):
        for i in range(v):
            for j in range(v):
                if g[i][k] == inf or g[k][j] == inf:
                    continue
                g[i][j] = min([g[i][j], g[i][k] + g[k][j]])
 
    for i in range(v):
        if g[i][i] != 0:
            print('NEGATIVE CYCLE')
            return
         
    for i in range(v):
        for j in range(v):
            if j > 0:
                print(' ', end='')
            if g[i][j] == inf:
                print('INF', end='')
            else:
                print(g[i][j], end='')
        print('')
 
if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input1'
 
with open(os.environ.get('INPUT') or '/dev/stdin') as f:
    input(f)
    solve()
 
if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input2'
 
    with open(os.environ.get('INPUT') or '/dev/stdin') as f:
        input(f)
        solve()
 
if os.environ.get('ZEPPELIN_HOME'):
    os.environ['INPUT'] = '/tmp/input3'
 
    with open(os.environ.get('INPUT') or '/dev/stdin') as f:
        input(f)
        solve()

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


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

min_dist = [[BIG_NUM]*V for i in range(V)]

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

for loop in range(E):
    tmp_from,tmp_to,tmp_cost = map(int,input().split())
    if min_dist[tmp_from][tmp_to] > tmp_cost:
        min_dist[tmp_from][tmp_to] = tmp_cost

for mid in range(V):
    for start in range(V):
        if min_dist[start][mid] == BIG_NUM:
            continue
        for goal in range(V):
            if min_dist[mid][goal] == BIG_NUM:
                continue
            if min_dist[start][goal] > min_dist[start][mid]+min_dist[mid][goal]:
                min_dist[start][goal] = min_dist[start][mid]+min_dist[mid][goal]


neg_FLG = False
#負閉路探し
for i in range(V):
    if min_dist[i][i] < 0:
        neg_FLG = True
        break


if neg_FLG == True:
    print("NEGATIVE CYCLE")
    sys.exit()

for row in range(V):
    if min_dist[row][0] == BIG_NUM:
        print("INF",end = "")
    else:
        print("%d"%(min_dist[row][0]),end = "")
    for col in range(1,V):
        if(min_dist[row][col] == BIG_NUM):
            print(" INF",end = "")
        else:
            print(" %d"%(min_dist[row][col]),end = "")
    print()

Submission status: Accepted

Solution code:
import sys

def floyd(v_count, matrix):
  for i in range(v_count):
    for j, c2 in enumerate(matrix[j][i] for j in range(v_count)):
      for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
        if c1 > c2+c3:
          matrix[j][k] = c2+c3
  return matrix

def has_negative_cycle(a):
  return any(row[i] < 0 for i, row in enumerate(a))

V, E = map(int,input().split())
inf = float("inf")
matrix = [[inf]*V for _ in [0]*V]
for i in range(V):
  matrix[i][i] =0
for s,t,d in (map(int, l.split()) for l in sys.stdin):
  matrix[s][t] = d
floyd(V, matrix)
if has_negative_cycle(matrix):
  print('NEGATIVE CYCLE')
else:
  for row in matrix:
    print(' '.join(map(lambda n:str(n) if n!=inf else "INF", row)))

Submission status: Accepted

Solution code:
from itertools import product
V,E = map(int,input().split())
edges = [tuple() for _ in range(E)]
dist = [[float("inf")]*V for _ in range(V)]
for i in range(V):
    dist[i][i] = 0
for _ in range(E):
    s,t,d = map(int,input().split())
    dist[s][t] = d
for k,i,j in product(range(V),range(V),range(V)):
    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])
for i in range(V):
    if dist[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit()
for i in range(V):
    ans = ["INF" if dist[i][j] == float("inf") else dist[i][j] for j in range(V)]
    print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
INFTY = 1 << 32

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


if __name__ == '__main__':
    n, e = [int(v) for v in input().split()]
    d = [[INFTY] * n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    for i in range(e):
        u, v, c = [int(v) for v in input().split()]
        d[u][v] = c

    floyd(n, d)

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

    if negative:
        print('NEGATIVE CYCLE')
    else:
        for i in range(n):
            line = []
            for j in range(n):
                if d[i][j] == INFTY:
                    line.append('INF')
                else:
                    line.append(str(d[i][j]))
            print(' '.join(line))

Submission status: Accepted

Solution code:
# Edige Weighted Digraph


from collections import namedtuple


WEIGHT_MAX = 10 ** 10
WeightedEdge = namedtuple('WeightedEdge', ('src', 'dest', 'weight'))


class Digraph:
    def __init__(self, v):
        self.v = v
        self.edges = [[] for _ in range(v)]

    def add(self, edge):
        self.edges[edge.src].append(edge)

    def adj(self, v):
        return self.edges[v]


def sp_bellmanford(graph, s):
    def relax(edge):
        s, t, w = edge
        if dists[t] > dists[s] + w:
            dists[t] = dists[s] + w
            srcs[t] = s
            _nodes.append(t)

    dists = [WEIGHT_MAX] * graph.v
    dists[s] = 0
    srcs = [-1] * graph.v
    nodes = []

    nodes.append(s)
    for _ in range(graph.v):
        _nodes = []
        for v in nodes:
            for e in graph.adj(v):
                relax(e)
        nodes = _nodes

    if len(nodes) > 0:
        return None
    else:
        return [None if dists[v] == WEIGHT_MAX else dists[v]
                for v in range(graph.v)]


def run():
    v, e = [int(i) for i in input().split()]

    graph = Digraph(v)
    for _ in range(e):
        edge = WeightedEdge(*[int(i) for i in input().split()])
        graph.add(edge)

    paths = []
    for r in range(v):
        ws = sp_bellmanford(graph, r)
        if ws is None:
            print("NEGATIVE CYCLE")
            break
        else:
            paths.append(ws)
    else:
        for ws in paths:
            print(" ".join("INF" if w is None else str(w) for w in ws))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
V, E = map(int, input().split())
INF = 10**20
cost = [[INF if x != y else 0 for x in range(V)] for y in range(V)]

for i in range(E) :
    a, b, c = map(int, input().split())
    cost[a][b] = c
    
for k in range(V) :
    for i in range(V) :
        for j in range(V) :
            if cost[i][k] != INF and cost[k][j] != INF :
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
            
negative_cycle = False 
for i in range(V) :
    if cost[i][i] < 0 :
        negative_cycle = True
        
if negative_cycle == True :
    print("NEGATIVE CYCLE")
else :
    for i in cost :
        i_str = list(map(str, i))
        print(" ".join([x if x != str(INF) else "INF" for x in i_str]))

Submission status: Accepted

Solution code:
from math import isinf
 
V, E = map(int, input().split())
d = [[float('inf') for i in range(V)] for j in range(V)]
 
for i in range(V):
    d[i][i] = 0
 
for i in range(E):
    s, t, w = map(int,input().split())
    d[s][t] = w
 
for k in range(V):
    for 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')
        exit()
 
for di in d:
    print(' '.join( ('INF' if isinf(dij) else str(dij) for dij in di)))

Submission status: Runtime Error

Solution code:
import heapq

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

def partial_solve(source,graph_data):
    heap = [(0,source)]
    partial_solution = [float("inf") for _ in range(4)]
    while heap:
        dist, target = heapq.heappop(heap)
        if partial_solution[target] > dist:
            if partial_solution[target] != float("inf"):
                return ["negative"]
            partial_solution[target] = dist
            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: Runtime Error

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
            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: Runtime Error

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=" ")
            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()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from sys import stdin


def generate_adj_table(v_table):
    for each in v_table:
        start, end, weight = map(int, each)
        init_adj_table[start][end] = weight

    return init_adj_table


def floyd():
    for k in _range:
        for i in _range:
            if adj_table[i].get(k) is None:
                adj_table[i][k] = float('INF')
                continue
            for j in _range:
                if adj_table[k].get(j) is None:
                    adj_table[k][j] = float("INF")
                    continue
                adj_table[i][j] = min(adj_table[i][j], adj_table[i][k] + adj_table[k][j])
    return adj_table


def solve():
    ans = floyd()
    negative = False
    for m in range(vertices):
        if ans[m][m] < 0:
            negative = True

    if negative:
        print('NEGATIVE CYCLE')
    else:
        for a in _range:
            print(*(str(each[-1]).upper() for each in sorted(ans[a].items())))

    return None


if __name__ == '__main__':
    _input = stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    info_list = map(lambda x: x.split(), _input[1:])
    _range = range(vertices)

    init_adj_table = tuple({i: 0} for i in range(vertices))
    adj_table = generate_adj_table(info_list)
    solve()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

vertice,edge = map(int,input().split(" "))
cost = [[0 if m == n else float("inf") for n in range(vertice)] for m in range(vertice)]
link = defaultdict(dict)
weight = defaultdict(dict)

for e in range(edge):
    i,j,w = map(int,input().split(""))
    link[i] = link.get(i,set()) | {j}
    weight[i].update({j:w})

vertice_cnt = 0
while 1:
    if vertice_cnt >= vertice:
        print("NEGATIVE CYCLE")
        break
    update = False
    for source in range(vertice)
        for k,value in link.items():
            for v in value:
                if cost[source][v] > cost[source][k] + weight[k][v]:
                    cost[source][v] = cost[source][k] + weight[k][v]
                    update = True
    if not update:
        for o in range(vertice):

            print(*([n if n != float("INF") else "INF" for n in cost[o]]))
        break
    vertice_cnt += 1

Submission status: Runtime Error

Solution code:
from collections import defaultdict

vertice,edge = map(int,input().split(" "))
cost = [[0 if m == n else float("inf") for n in range(vertice)] for m in range(vertice)]
link = defaultdict(dict)
weight = defaultdict(dict)

for e in range(edge):
    i,j,w = map(int,input().split(""))
    link[i] = link.get(i,set()) | {j}
    weight[i].update({j:w})

vertice_cnt = 0
while 1:
    if vertice_cnt >= vertice:
        print("NEGATIVE CYCLE")
        break
    update = False
    for source in range(vertice):
        for k,value in link.items():
            for v in value:
                if cost[source][v] > cost[source][k] + weight[k][v]:
                    cost[source][v] = cost[source][k] + weight[k][v]
                    update = True
    if not update:
        for o in range(vertice):

            print(*([n if n != float("INF") else "INF" for n in cost[o]]))
        break
    vertice_cnt += 1

Submission status: Runtime Error

Solution code:
from collections import defaultdict
vertices, edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
cost_dp = [[float("inf") if n != m else 0 for n in range(vertices)] for m in range(vertices)]
for e in range(edges):
    v1, v2, weight = (int(n) for n in input().split(" "))
    connect[v1].append([v2,weight])
    connect[v2].append([v1,weight])
    cost_dp[v1][v2] = weight
for neg in range(2):
    updated = 0
    for t in range(vertices + 1):
        for i in range(vertices):
            for k in range(vertices):
                if cost_dp[i][k] > cost_dp[i][t] + cost_dp[t][k]:
                    updated = 1
                    cost_dp[i][k] = cost_dp[i][t] + cost_dp[t][k]
if neg == 1 and updated:
    print("NEGATIVE CYCLE")
else:
    for ve in range(vertices):
        ans = ["INF" if n == float("inf") else n for n in cost_dp[ve]]
        print(*ans)
    break

Submission status: Runtime Error

Solution code:
from collections import defaultdict
vertices, edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
cost_dp = [[float("inf") if n != m else 0 for n in range(vertices)] for m in range(vertices)]
for e in range(edges):
    v1, v2, weight = (int(n) for n in input().split(" "))
    connect[v1].append([v2,weight])
    connect[v2].append([v1,weight])
    cost_dp[v1][v2] = weight
for neg in range(2):
    updated = 0
    for t in range(vertices):
        for i in range(vertices):
            for k in range(vertices):
                if cost_dp[i][k] > cost_dp[i][t] + cost_dp[t][k]:
                    updated = 1
                    cost_dp[i][k] = cost_dp[i][t] + cost_dp[t][k]
if neg == 1 and updated:
    print("NEGATIVE CYCLE")
else:
    for ve in range(vertices):
        ans = ["INF" if n == float("inf") else n for n in cost_dp[ve]]
        print(*ans)
    break

Submission status: Runtime Error

Solution code:
def main():
    INF = int(1e12)
    G = [[0 for i in range(101)] for j in range(101)];
 
    v, e = map(int, raw_input().split())
 
    for i in range(v):
        for j in range(v):
            if i == j:
                G[i][j] = 0
            else:
                G[i][j] = INF
 
    for i in range(e):
        s, t, d = map(int, raw_input().split())
        G[s][t] = d
 
    for k in range(v):
        for i in range(v):
            c2 = G[i][k]
            for j, (c1, c3) in enumerate(zip(G[i], G[k])):
                if ci > c2 + c3:
                    G[i][j] = c2 + c3
                    G[i][j] = min(G[i][j], G[i][k] + G[k][j])
 
    for i in range(v):
        if G[i][i] < 0:
            print "NEGATIVE CYCLE"
            return 0
 
    for i in range(v):
        ans = []
 
        for j in range(v):
            if G[i][j] == INF:
                ans.append("INF")
            else:
                ans.append(G[i][j])
 
        print " ".join(map(str, ans))
 
main()

Submission status: Runtime Error

Solution code:
def main():
    INF = int(1e12)
    G = [[0 for i in range(101)] for j in range(101)];
  
    v, e = map(int, raw_input().split())
  
    for i in range(v):
        for j in range(v):
            if i == j:
                G[i][j] = 0
            else:
                G[i][j] = INF
  
    for i in range(e):
        s, t, d = map(int, raw_input().split())
        G[s][t] = d
  
    for k in range(v):
        for i in range(v):
            c2 = G[i][k]
            for j, (c1, c3) in enumerate(zip(G[i], G[k])):
                if ci > c2 + c3:
                    G[i][j] = c2 + c3

    for i in range(v):
        if G[i][i] < 0:
            print "NEGATIVE CYCLE"
            return 0
  
    for i in range(v):
        ans = []
  
        for j in range(v):
            if G[i][j] == INF:
                ans.append("INF")
            else:
                ans.append(G[i][j])
  
        print " ".join(map(str, ans))
  
main()

Submission status: WA: Presentation Error

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):
    for j in range(V):
        print(dist[i][j] if dist[i][j] != INF else "INF",end=" ")
    print()

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