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:
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') 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()

Submission status: Wrong Answer

Solution code:
import sys

def warshall(n, matrix):
  for i in xrange(n):
    matrix[i][i] = 0
  for i in xrange(n):
    for j in xrange(n):
      for k in xrange(n):
        matrix[j][k] = min(matrix[j][k], matrix[j][i]+matrix[i][k])
  return matrix

V,E = map(int, raw_input().split())
path = [[sys.maxint] * V for _ in xrange(V)]
for _ in xrange(E):
  s,t,d = map(int, raw_input().split())
  path[s][t] = d
cost = warshall(V, path)
isNegative = False
for i in xrange(V):
  if cost[i][i] < 0:
    isNegative = True
    break

if isNegative:
  print "NEGATIVE CYCLE"
else:
  for i in xrange(V):
    printlist = []
    for j in xrange(V):
      if cost[i][j] == sys.maxint:
        printlist.append("INF")
      else:
        printlist.append(str(cost[i][j]))
    print " ".join(printlist)

Submission status: Wrong Answer

Solution code:
import sys

f_i = sys.stdin

max_d = 2 * 10 ** 7 + 1

V, E = map(int, f_i.readline().split())

# adjacency matrix
A = [[max_d] * i + [0] + [max_d] * (V - i - 1) for i in range(V)]

for l_i in f_i:
    s, t, d = map(int, l_i.split())
    A[s][t] = d

# Warshall???Floyd Algorithm
for k in range(V - 1):
    for i in range(V):
        for j in range(V):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])

for i in range(V):
    for j in range(V):
        e = min(A[i][j], A[i][V - 1] + A[V - 1][j])
        if e == max_d:
            A[i][j] = "INF"
        else:
            A[i][j] = e


# check whether A has negative cycle
flag = 1
for k in range(V):
    if A[k][k] < 0:
        flag = 0
        print("NEGATIVE CYCLE")
        break

# Output
if flag:
    for a in A:
        print(*a)

Submission status: Wrong Answer

Solution code:
nv, ne = map(int, input().split(' '))
edges = []
for i in range(ne):
    s, t, w = map(int, input().split(' '))
    edges.append((s, t, w))

dist = [[float('inf')] * nv for i in range(nv)]
for i in range(nv):
    dist[i][i] = 0
for s, t, w in edges:
    dist[s][t] = w

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

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

[print(' '.join(map(str, dist[i]))) for i in range(nv)]

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

inf = 1<<30

def solve():
    N, M = map(int, sys.stdin.readline().split())

    cost = [[inf]*N for i in range(N)]
    for u in range(N):
        cost[u][u] = 0

    for i in range(M):
        si, ti, di = map(int, sys.stdin.readline().split())
        cost[si][ti] = di

    res = WarshallFloyd(N, cost)

    if res is None:
        print('NEGATIVE CYCLE')
    else:
        for i in range(N):
            print(*[res[i][j] if res[i][j] < inf else 'INF' for j in range(N)])


def WarshallFloyd(N, cost):
    dist = [[inf]*N for i in range(N)]

    for i in range(N):
        for j in range(N):
            dist[i][j] = cost[i][j]

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

    if any(dist[i][i] < 0 for i in range(N)):
        return None
    else:
        return dist

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

inf = 1<<30

def solve():
    N, M = map(int, sys.stdin.readline().split())

    cost = [[inf]*N for i in range(N)]
    for u in range(N):
        cost[u][u] = 0

    for i in range(M):
        si, ti, di = map(int, sys.stdin.readline().split())
        cost[si][ti] = di

    res = WarshallFloyd(N, cost)

    if res is None:
        print('NEGATIVE CYCLE')
    else:
        for i in range(N):
            print(*[res[i][j] if res[i][j] < inf else 'INF' for j in range(N)])


def WarshallFloyd(N, cost):
    dist = [[inf]*N for i in range(N)]

    for i in range(N):
        for j in range(N):
            dist[i][j] = cost[i][j]

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dist[i][k] < inf and dist[k][j] < inf:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    if any(dist[i][i] < 0 for i in range(N)):
        return None
    else:
        return dist

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

V, E = map(int, readline().split())
inf = 10**10
vertices = [[inf if i!=j else 0 for j in range(V)] for i in range(V)]

for _ in [None]*E:
    s, t, d = map(int, readline().split())
    vertices[s][t] = d

for i in range(V):
    for j in range(V):
        for k in range(V):
            c1, c2, c3 = vertices[i][k], vertices[i][j], vertices[j][k]
            if c2 != inf and c3 != inf:  # for Negative Edge
                vertices[i][k] = c1 if c1 < c2+c3 else c2+c3

ans = []
for i, a in enumerate(vertices):
    if a[i] < 0:
        print("NEGATIVE CYCLE")
        break
    ans.append(" ".join([str(n) if n != inf else "INF" for n in a]))
else:
    print("\n".join(ans))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

INF = 999999999999999999999

def bellman_ford(G, n):
  d = {}
  for i in range(n):
    d[i] = {}
    for j in range(n):
      if i in G and j in G[i]:
        d[i][j] = G[i][j]
      else:
        d[i][j] = INF
    d[i][i] = 0
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if d[i][j] > d[i][k] + d[k][j]:
          d[i][j] = d[i][k] + d[k][j]
  return d

G = {}

n, m = [int(v) for v in input().strip().split(' ')]
for i in range(n):
  G[i] = {}
for _ in range(m):
  s, t, c = [int(v) for v in input().strip().split(' ')]
  G[s][t] = c

d = bellman_ford(G, n)

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

for i in range(n):
  print(" ".join([str(d[i][j]) if d[i][j] != INF else "INF" for j in range(n)]))

Submission status: Wrong Answer

Solution code:
# Warshall-Floyds Method (O|V3|)

V, E = map(int, input().split())
INF = 1e12
d = [[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')
        break

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

Submission status: Wrong Answer

Solution code:
V, E = map(int, input().split())
INF = 1e12
d = [[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 dij == INF else str(dij) for dij in di)))

Submission status: Wrong Answer

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
updated = 0
for t in range(vertices + 1):
    if t == vertices:
        print("NEGATIVE CYCLE")
        break
    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 not updated:
        for ve in range(vertices):
            ans = ["INF" if n == float("inf") else n for n in cost_dp[ve]]
            print(*ans)
        break

Submission status: Wrong Answer

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

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

    diag = [adj[i][i]==abs(adj[i][i]) for i in xrange(V)]
    if False in diag:
        print "NEGATIVE CYCLE"
    else:
        for item in adj:
            for d in item:
                print d,
            print ""

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def WarshallFloyd(G):
    V = len(G)
    for k in range(V):
        for i in range(V):
            for j in range(V):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

D = WarshallFloyd(D)

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

Submission status: Wrong Answer

Solution code:


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


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

for i in range(n):
    d[i][i] =0
            
for i in range(q):    
    s=[int(x) for x in input().split()]
    d[s[0]][s[1]]=s[2]
    
floyd()

    # 判断是否存在负环
negative = False;
for i in range(n):
    if (d[i][i] < 0):
        negative = True;

if (negative):
    print("NEGATIVE CYCLE");
else :
    for i in range(n): 
        for j in range(n):
            if (d[i][j] == INF):
                    print("INF",end=' ')
            else:
                if j!=n-1:print("%d"%(d[i][j]),end=' ')
                else: print("%d"%(d[i][j]))

Submission status: Wrong Answer

Solution code:
node_size, edge_size = [int(x) for x in input().split()]
INF = 10**10
distance = [[INF for _ in range(node_size)] for _ in range(node_size)]

for i in range(node_size):
    distance[i][i] = 0

for i in range(edge_size):
    link_from, link_to, link_distance = [int(x) for x in input().split()]
    distance[link_from][link_to] = link_distance

for i in range(node_size):
    for j in range(node_size):
        for k in range(node_size):
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

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

for i in range(node_size):
    print(' '.join('INF' if x == INF else str(x) for x in distance[i]))

Submission status: Time Limit Exceeded

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[fr] == INF:
                continue
            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: Time Limit Exceeded

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] != 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)]
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: Time Limit Exceeded

Solution code:
INF = 1000000000

def BellmanFord_edge(s, v, edge):
    dp = [INF] * v
    dp[s] = 0
    for i in range(0, v):
        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
    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: Time Limit Exceeded

Solution code:
nv, ne = map(int, input().split(' '))
edges = []
for i in range(ne):
    s, t, w = map(int, input().split(' '))
    edges.append((s, t, w))

for r in range(nv):
    dist = [float('inf')] * nv
    dist[r] = 0

    for i in range(nv - 1):
        for s, t, w in edges:
            if dist[t] > dist[s] + w:
                dist[t] = dist[s] + w

    for s, t, w in edges:
        if dist[t] > dist[s] + w:
            print("NEGATIVE CYCLE")
            exit()

    print(' '.join([str(d) if d < float('inf') else "INF" for d in dist]))

Submission status: Time Limit Exceeded

Solution code:
import math
import heapq

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

result = [[math.inf] * V for _ in range(V)]

edges = []
for _ in range(E):
    edge = list(map(int, input().strip().split()))
    edges.append(edge)

negative_cycle = False
for start in range(V):
    if negative_cycle:
        break
    for target in range(V):
        if negative_cycle:
            break
        cost = [math.inf] * V
        cost[start] = 0
        for n in range(V-1):
            update = False
            for src, dest, weight in edges:
                if cost[dest] > cost[src] + weight:
                    cost[dest] = cost[src] + weight
                    update = True
            if not update:
                break

        for src, dest, weight in edges:
            if cost[dest] >  cost[src] + weight:
                negative_cycle = True
                break

        result[start][target] = cost[target]
if negative_cycle:
    print("NEGATIVE CYCLE")
else:
    for res in result:
        print(' '.join(map(lambda d:str(d).upper(), res)))

Submission status: Accepted

Solution code:
import sys

def warshall_floyd(v_count, matrix):
    for i in range(v_count):
        for j in range(v_count):
            c2 = matrix[j][i]
            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) -> bool:
    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
warshall_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:
import sys

def warshall_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) -> bool:
    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
warshall_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:
import sys

def warshall_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, (_, c3) in filter(lambda x: x[1][0] > c2+x[1][1], enumerate(zip(matrix[j], matrix[i]))):
                matrix[j][k] = c2+c3
    return matrix


def has_negative_cycle(a) -> bool:
    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
warshall_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:
import sys

def warshall_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 zip(range(v_count), matrix[j], matrix[i]):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix


def has_negative_cycle(a) -> bool:
    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
warshall_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:
import sys

def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    :param v_count: 頂点数
    :param 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
    return matrix


def has_negative_cycle(matrix: list) -> bool:
    """ 負閉路チェック
    :param matrix: 隣接行列(ワーシャルフロイドの結果)
    """
    return any(row[i] < 0 for i, row in enumerate(matrix))


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
warshall_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:
import sys

def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    :param v_count: 頂点数
    :param matrix: 隣接行列
    """
    for i in range(v_count):
        for j, c2 in ((j, 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(matrix: list) -> bool:
    """ 負閉路チェック
    :param matrix: 隣接行列(ワーシャルフロイドの結果)
    """
    return any(row[i] < 0 for i, row in enumerate(matrix))


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
warshall_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 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, v):
    NEGATIVE = False
    for i in range(v):
        if A[i][i] < 0:
            NEGATIVE = True
    if NEGATIVE:
        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)
A = worshall_floyd(A, v)
print_ans(A, v)

Submission status: Accepted

Solution code:
from sys import exit
INF = 1<<32
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: Accepted

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 ans[i][k] == INF:
            continue
        for j in range(v):
            if ans[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: Accepted

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):
    for j in range(N):
        if ans[i][j]==INF:
            ans[i][j]='INF'
for i in range(N):
    print(*ans[i])

Submission status: Accepted

Solution code:
INF = 999999999999

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: Accepted

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):
                if dist[i][k] != inf and dist[k][j] != inf:
                    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()