0146 - graph

Călinuţa tocmai a găsit o foaie de hârtie pe care este desenat un graf orientat aciclic cu N noduri şi M arce, fiecare arc având o distanţă de valoare întreagă.

Cerință

Dându-se N, M şi cele M arce cu distanţele dintre ele, trebuie să calculaţi pentru Călinuţa distanţa minimă dintre fiecare două noduri.

Date de intrare

Fișierul de intrare graph.in conține pe prima linie numerele naturale N și M separate printr-un singur spațiu, iar pe următoarele M linii se află câte 3 numere A, B şi C, reprezentând un arc de la A către B de lungime C.

Date de ieșire

Fișierul de ieșire graph.out conține N linii cu câte N valori separate prin câte un spaţiu, reprezentând matricea drumurilor minime. Dacă nu există drum de la un nod a la un nod b, valoarea care trebuie afişată este x.

Restricții și precizări:

• N ≤ 1500
• M ≤ 30.000
• Numerele nodurilor sunt valori cuprinse între 1 şi N
• Lungimea arcelor aparţine intervalului [-1000; 1000]
• Pentru 25% din teste N ≤ 150 şi M ≤ 1000
• Pentru alte 40% din teste N ≤ 1000

Exemplu

graph.in

8 9
1 2 7
2 3 -1
2 4 -2
2 7 3
8 2 -2
8 6 3
5 4 2
5 6 6
6 7 -5

graph.out

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

Rezolvare

def floyd_warshall(graph, N):
    distances = [[float('inf')] * N for _ in range(N)]

    for i in range(N):
        distances[i][i] = 0

    for u, v, w in graph:
        distances[u - 1][v - 1] = w

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if distances[i][k] != float('inf') and distances[k][j] != float('inf'):
                    distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])

    return distances

def main():
    with open("graph.in", "r") as fin:
        N, M = map(int, fin.readline().split())
        graph = [tuple(map(int, fin.readline().split())) for _ in range(M)]

    distances = floyd_warshall(graph, N)

    with open("graph.out", "w") as fout:
        for row in distances:
            fout.write(" ".join(map(lambda x: str(x) if x != float('inf') else "x", row)) + "\n")

if __name__ == "__main__":
    main()