0589 - Roy-Floyd: Diferență între versiuni
De la Universitas MediaWiki
(Pagină nouă: = 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...) |
(Nicio diferență)
|
Versiunea curentă din 18 mai 2024 20:15
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()