Oros Ioana Diana: Pagină nouă: = 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...

2024-05-18T20:15:58Z

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...

New page

= 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>

0589 - Roy-Floyd - Revision history