0589 - Roy-Floyd

Cerința

Se dă un graf orientat ponderat cu n noduri și m arce – în care fiecare arc are asociat un cost, număr natural strict pozitiv. Folosind algoritmul Roy-Floyd, construiți matricea costurilor minime, a[i][j] fiind costul minim al unui drum de la i la j, dacă există un asemenea drum, sau -1 în caz contrar.

Date de intrare

Fișierul de intrare roy-floydIN.txt conține pe prima linie numerele n m, iar următoarele linii câte un triplet i j c, cu semnificația: există arcul (i j) și are costul c.

Date de ieșire

Fișierul de ieșire roy-floydOUT.txt va conține matricea construită, câte o linie a matricei pe o linie a fișierului, elementele de pe fiecare linie fiind separate prin exact un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 100
• costul unui arc va fi mai mic decât 1000
• costul unui drum este egal cu suma costurilor arcelor care îl compun

Exemplu:

roy-floydIN.txt

5 6
1 3 1
2 1 2
4 2 1
4 3 8
5 3 5
5 4 2

roy-floydOUT.txt

0 -1 1 -1 -1 
2 0 3 -1 -1 
-1 -1 0 -1 -1 
3 1 4 0 -1 
5 3 5 2 0 

Rezolvare

<syntaxhighlight lang="python" line="1"> INFINIT = 1000000000

def verifica_restrictii(n, m, costuri):

   if not (1 <= n <= 100):
       return False
   if any(c >= 1000 for _, _, c in costuri):
       return False
   return True

def roy_floyd():

   try:
       with open("roy-floydIN.txt", "r") as fin:
           linie = fin.readline().strip()
           if not linie:
               raise ValueError("Linia de intrare este goala.")
           n, m = map(int, linie.split())
           costuri = [tuple(map(int, fin.readline().split())) for _ in range(m)]
   except ValueError as e:
       with open("roy-floydOUT.txt", "w") as fout:
           fout.write(f"Datele nu corespund restrictiilor impuse: {e}")
       return

   if not verifica_restrictii(n, m, costuri):
       with open("roy-floydOUT.txt", "w") as fout:
           fout.write("Datele nu corespund restrictiilor impuse")
       return

   a = [[INFINIT] * (n + 1) for _ in range(n + 1)]
   
   for i in range(1, n + 1):
       a[i][i] = 0
   
   for i, j, c in costuri:
       a[i][j] = c
   
   for k in range(1, n + 1):
       for i in range(1, n + 1):
           for j in range(1, n + 1):
               if a[i][j] > a[i][k] + a[k][j]:
                   a[i][j] = a[i][k] + a[k][j]
   
   with open("roy-floydOUT.txt", "w") as fout:
       for i in range(1, n + 1):
           for j in range(1, n + 1):
               fout.write(f"{-1 if a[i][j] == INFINIT else a[i][j]} ")
           fout.write("\n")

if __name__ == "__main__":

   roy_floyd()

</syntaxhighlight>