View source for 0589 - Roy-Floyd

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

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

= Date de ieșire =
Fișierul de ieșire <code>roy-floydOUT.txt</code> 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 =

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

= Exemplu: =
<code>roy-floydIN.txt</code>
 5 6
 1 3 1
 2 1 2
 4 2 1
 4 3 8
 5 3 5
 5 4 2
<code>roy-floydOUT.txt</code>
 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>