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

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()