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:
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] > 10 ** 12:
        printlist.append("INF")
      else:
        printlist.append(str(cost[i][j]))
    print " ".join(printlist)

Submission status: Accepted

Solution code:
import sys

f_i = sys.stdin

max_d = float("inf")

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

Solution code:
import sys

f_i = sys.stdin

max_d = float("inf")

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):
    for i in range(V):
        for j in range(V):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])

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

# Output
if not is_negative:
    for a in A:
        print(*[str(e).upper() for e in a])

Submission status: Accepted

Solution code:
import sys

f_i = sys.stdin

max_d = float("inf")

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):
    for i in range(V):
        for j in range(V):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])

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

# Output
import math

if not is_negative:
    for a in A:
        print(' '.join(('INF' if math.isinf(Aij) else str(Aij) for Aij in a)))

Submission status: Accepted

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:
            for j in _range:
                adj_table[i][j] = min(adj_table[i].get(j, float("INF")),
                                      adj_table[i].get(k, float("INF")) + adj_table[k].get(j, float("INF")))
    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: Accepted

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

from sys import stdin
from math import isinf


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

    return _init_adj_table


def floyd(_adj_table):
    for k in _range:
        for i in _range:
            for j in _range:
                _adj_table[i][j] = min(_adj_table[i][j],
                                       _adj_table[i][k] + _adj_table[k][j])
    return _adj_table


def solve(_adj_table):
    after_floyd_table = floyd(_adj_table)

    negative = False
    for m in _range:
        if after_floyd_table[m][m] < 0:
            negative = True

    if negative:
        print('NEGATIVE CYCLE')
        return None
    else:
        for each in after_floyd_table:
            print(' '.join(('INF' if isinf(ele) else str(ele) for ele in each)))

    return after_floyd_table


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([float('inf')] * vertices for i in range(vertices))
    for n in _range:
        init_adj_table[n][n] = 0

    adj_table = generate_adj_table(info_list, init_adj_table)
    solve(adj_table)

Submission status: Accepted

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

from sys import stdin
from math import isinf


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

    return _init_adj_table


def floyd(_adj_table):
    for k in v_range:
        for i in v_range:
            for j in v_range:
                _adj_table[i][j] = min(_adj_table[i][j],
                                       _adj_table[i][k] + _adj_table[k][j])
    return _adj_table


def solve(_after_table):
    negative = False
    for m in v_range:
        if _after_table[m][m] < 0:
            negative = True

    if negative:
        print('NEGATIVE CYCLE')
        return None
    else:
        for each in _after_table:
            print(' '.join(('INF' if isinf(ele) else str(ele) for ele in each)))

    return _after_table


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

    init_adj_table = tuple([float('inf')] * vertices for _ in v_range)
    for n in v_range:
        init_adj_table[n][n] = 0

    adj_table = generate_adj_table(info_list, init_adj_table)
    after_table = floyd(adj_table)
    solve(after_table)

Submission status: Accepted

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

from sys import stdin
from math import isinf


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

    return _init_adj_table


def floyd(_adj_table):
    for k in v_range:
        for i in v_range:
            for j in v_range:
                _adj_table[i][j] = min(_adj_table[i][j],
                                       _adj_table[i][k] + _adj_table[k][j])
    return _adj_table


def solve(_after_table):
    negative = False
    for m in v_range:
        if _after_table[m][m] < 0:
            negative = True

    if negative:
        print('NEGATIVE CYCLE')
        return None
    else:
        for each in _after_table:
            print(' '.join(('INF' if isinf(ele) else str(ele) for ele in each)))

    return _after_table


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

    init_adj_table = tuple([float('inf')] * vertices for _ in v_range)
    for n in v_range:
        init_adj_table[n][n] = 0

    adj_table = generate_adj_table(info_list, init_adj_table)
    after_table = floyd(adj_table)
    ans = solve(after_table)

Submission status: Accepted

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

for row in dist:
    print(' '.join(str(d) if d < float('inf') else 'INF' for d in row))

Submission status: Accepted

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

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

import sys
import os
import pprint

"""???????????£????????????????????¨??????"""

MAX = 100
d = [[None for i in range(MAX)] for j in range(MAX)]

for i in range(MAX):
    for j in range(MAX):
        if i == j:
            d[i][j] = 0
        else:
            d[i][j] = float('inf')


#fd = os.open('GRL_1_C.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

V, E = list(map(int, input().split()))
for i in range(E):
    start, end, weight = list(map(int, input().split()))
    d[start][end] = weight

# floyd
for k in range(V):
    for i in range(V):
        for j in range(V):
            if d[i][k] == float('inf'):
                continue
            elif d[k][j] == float('inf'):
                continue
            else:
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])


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

if negative:
    print('NEGATIVE CYCLE')
else:
    for i in range(V):
        for j in range(V):

            if d[i][j] == float('inf'):
                print("INF", end="")
            else:
                print(d[i][j], end='')
            if j != V - 1:
                print(' ', end='')
            else:
                print('')

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

inf = 1<<60

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

Solution code:
import sys

inf = float('inf')

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

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

d = [[0 if i == j else inf for i in range(V)] for j in range(V)]

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

def wf():
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
wf()

flag = True
for i in range(V):
    if d[i][i] < 0:
        flag = False
        break
if flag:
    for i in range(V):
        print(" ".join("INF" if j == inf else str(j) for j in d[i]))
else: print("NEGATIVE CYCLE")

Submission status: Accepted

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 k in range(V):
    for i in range(V):
        for j in range(V):
            c1, c2, c3 = vertices[i][j], vertices[i][k], vertices[k][j]
            if c2 != inf and c3 != inf:  # for Negative Edge
                vertices[i][j] = 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: Accepted

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

V, E = map(int, readline().split())
inf = float("inf")
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 k in range(V):
    for i in range(V):
        for j in range(V):
            c1, c2, c3 = vertices[i][j], vertices[i][k], vertices[k][j]
            vertices[i][j] = 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: Accepted

Solution code:
def main():
    nvertices, nedges = map(int, input().split())
    INF = float('inf')
    D1 = [[INF for i in range(nvertices)] for i in range(nvertices)]
    for i in range(nedges):
        s, t, d = map(int, input().split())
        D1[s][t] = d

    for i in range(nvertices):
        D1[i][i] = 0

    for k in range(nvertices):
        D2 = [[INF for i in range(nvertices)] for i in range(nvertices)]
        for i in range(nvertices):
            for j in range(nvertices):
                D2[i][j] = min(D1[i][j], D1[i][k] + D1[k][j])
        D1 = D2

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

    for lst in D1:
        print(" ".join(map(lambda e: str(e) if e < INF else "INF", lst)))


main()

Submission status: Accepted

Solution code:
from sys import stdin
MAX = 100
INF = 1<<32
n, e = map(int, stdin.readline().split())
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(e):
    u, v, c = map(int, stdin.readline().split())
    d[u][v] = c
def floyd():
    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
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
floyd()
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit(0)
for i in range(n):
    for j in range(n):
        if d[i][j] == INF: print("INF", end="")
        else: print(d[i][j], end="")
        if j + 1 != n:
            print(" ", end="")
    print()

Submission status: Accepted

Solution code:
from sys import stdin
from math import isinf
n, e = map(int, stdin.readline().split())
d = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(e):
    u, v, c = map(int, stdin.readline().split())
    d[u][v] = c
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]
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit(0)
for di in d:
    print(' '.join(('INF' if isinf(dij) else str(dij) for dij in di)))

Submission status: Accepted

Solution code:
from sys import stdin
from math import isinf
n, e = map(int, stdin.readline().split())
d = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(e):
    u, v, c = map(int, stdin.readline().split())
    d[u][v] = c
for k in range(n):
    for i in range(n):
        if d[i][k] == float('inf'): continue
        for j in range(n):
            if d[k][j] == float('inf'): continue
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit(0)
for di in d:
    print(' '.join(('INF' if isinf(dij) else str(dij) for dij in di)))

Submission status: Accepted

Solution code:
from sys import stdin
from math import isinf
import itertools
n, e = map(int, stdin.readline().split())
d = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(e):
    u, v, c = map(int, stdin.readline().split())
    d[u][v] = c
for k, i, j in itertools.product(range(n), repeat=3):
    if d[i][j] > d[i][k] + d[k][j]:
        d[i][j] = d[i][k] + d[k][j]
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit(0)
for di in d:
    print(' '.join(('INF' if isinf(dij) else str(dij) for dij in di)))

Submission status: Accepted

Solution code:
from sys import stdin
from math import isinf
import itertools
n, e = map(int, stdin.readline().split())
d = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(e):
    u, v, c = map(int, stdin.readline().split())
    d[u][v] = c
for k, i, j in itertools.product(range(n), repeat=3):
    if d[i][j] > d[i][k] + d[k][j]:
        d[i][j] = d[i][k] + d[k][j]
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit(0)
for di in d:
    print(*['INF' if isinf(dij) else str(dij) for dij in di])

Submission status: Accepted

Solution code:
import math


def main():
    nvertices, nedges = map(int, input().split())
    INF = float('inf')
    D1 = [[0 if i == j else INF for i in range(nvertices)]
          for j in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        D1[u][v] = w

    for k in range(nvertices):
        D2 = [[0] * nvertices for i in range(nvertices)]
        for i in range(nvertices):
            for j in range(nvertices):
                D2[i][j] = min(D1[i][j], D1[i][k] + D1[k][j])
        D1 = D2

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

    for D in D1:
        print(" ".join(map(lambda e: "INF" if math.isinf(e) else str(e), D)))


main()

Submission status: Accepted

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][k] == INF or d[k][j] == INF:
          continue
        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: Accepted

Solution code:
def main():
    nvertices, nedges = map(int, input().split())
    INF = float('inf')
    W = [[0 if i == j else INF for i in range(nvertices)] for j in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        W[u][v] = w

    for k in range(nvertices):
        for i in range(nvertices):
            for j in range(nvertices):
                W[i][j] = min(W[i][j], W[i][k] + W[k][j])

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

    for lst in W:
        print(" ".join(map(lambda e: str(e) if e < INF else "INF", lst)))


main()

Submission status: Accepted

Solution code:
import random


def main():
    nvertices, nedges = map(int, input().split())
    INF = float('inf')
    W = [[0 if i == j else INF for i in range(nvertices)] for j in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        W[u][v] = w

    lst = [i for i in range(nvertices)]
    random.shuffle(lst)
    for k in lst:
        for i in range(nvertices):
            for j in range(nvertices):
                W[i][j] = min(W[i][j], W[i][k] + W[k][j])

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

    for lst in W:
        print(" ".join(map(lambda e: str(e) if e < INF else "INF", lst)))


main()

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

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=jp
"""
import sys


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])


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

    is_nagative = False
    for i in range(V):
        if dp[i][i] < 0:
            is_nagative = True
    if is_nagative:
        print('NEGATIVE CYCLE')
    else:
        for d in dp:
            print(' '.join(map(str, d)).replace('inf', 'INF'))


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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
    D[t][t] = d

for v in range(V):
    D[v][v] = 0 

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

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

Submission status: Accepted

Solution code:
v,e = map(int, input().split())
G = [[float('inf')] * v for i in range(v)]
for i in range(v):
    G[i][i] = 0
for i in range(e):
    s,t,d = map(int, input().split())
    G[s][t] = d

for i in range(v):
    for j in range(v):
        for k in range(v):
            G[j][k] = min(G[j][k], G[j][i]+G[i][k])

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

for row in G:
    row = map(lambda x: 'INF' if x == float('inf') else str(x),row)
    print(' '.join(row))

Submission status: Accepted

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)

Submission status: Accepted

Solution code:
vertices, edges = (int(n) for n in input().split(" "))
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(" "))
    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)

Submission status: Accepted

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):
            for j in range(v):
                if G[i][k] != INF and G[k][j] != INF:
                    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: 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)]
# d = []
# a = []
# for i in range(V):
#     a.append(float('INF'))
#
# for j in range(V):
#     d.append(a)


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

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 i in xrange(V):
                d = item[i]
                if i!=V-1:
                    if d==float("inf"):
                        print "INF",
                    else:
                        print d,
                else:                    
                    if d==float("inf"):
                        print "INF"
                    else:
                        print d

if __name__ == "__main__":
    main()