Cod sursa(job #2449064)
Utilizator | Data | 18 august 2019 00:45:02 | |
---|---|---|---|
Problema | Floyd-Warshall/Roy-Floyd | Scor | 20 |
Compilator | py | Status | done |
Runda | Arhiva educationala | Marime | 0.47 kb |
#!/usr/bin/env python3
import sys, itertools
sys.stdout = open('royfloyd.out', 'w')
with open('royfloyd.in', 'r') as fin:
N = int(fin.readline())
A = [list(map(int, fin.readline().split())) for _ in range(N)]
D = [A[i][:] for i in range(N)]
for k, i, j in itertools.product(range(N), range(N), range(N)):
if D[i][k] * D[k][j] > 0:
D[i][j] = min(D[i][j], D[i][k] + D[k][j])
for i in range(N):
print(' '.join(map(str, D[i])))