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

<syntaxhighlight lang="python3"> 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()

</syntaxhighlight>