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: WA: Presentation Error

Solution code:
import sys

inf = int(1e12)

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

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

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

    for i in range(v):
        for j in range(v):
            if dist_mat[i][j] >= inf:
                sys.stdout.write("INF ")
            else:
                sys.stdout.write(str(dist_mat[i][j]) + " ")
        print("")

main()

Submission status: WA: Presentation Error

Solution code:
import sys

inf = int(1e12)

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

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

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

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

main()

Submission status: WA: Presentation Error

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(str(d) + ' ', end='') if d < float('inf') else print("INF ", end='') for d in dist]
    print()

Submission status: WA: Presentation Error

Solution code:
import queue
import math

def warshall(graph, n):
    for i in range(n):
        graph[i][i] = 0

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

    return graph


def main():
    n, m = map(int, input().split())
    graph = [[float('inf') for _ in range(n)] for _ in range(n)]

    for _ in range(m):
        data = list(map(int, input().split()))

        graph[data[0]][data[1]] = data[2]

    dist = warshall(graph, n)

    for y in dist:
        for x in y:
            if x < 0:
                print("NEGATIVE CYCLE")
                return

    for y in dist:
        for x in y:
            print('{} '.format(x if x != float('inf') else 'INF'), end="")
        print()

    return


if __name__ == '__main__':
    main()

Submission status: WA: Presentation Error

Solution code:
import queue
import math


def warshall(graph, n):
    for i in range(n):
        graph[i][i] = 0

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

    return graph


def main():
    n, m = map(int, input().split())
    graph = [[float('inf') for _ in range(n)] for _ in range(n)]

    for _ in range(m):
        data = list(map(int, input().split()))

        graph[data[0]][data[1]] = data[2]

    dist = warshall(graph, n)

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

    for y in dist:
        for x in y:
            print('{} '.format(x if x != float('inf') else 'INF'), end="")
        print()

    return


if __name__ == '__main__':
    main()

Submission status: WA: Presentation Error

Solution code:
def floyd():
    global d
    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<< 30
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\n");
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]))