Danciu: Pagină nouă: Călinuţa tocmai a găsit o foaie de hârtie pe care este desenat un graf orientat aciclic cu `N` noduri şi `M` arce, fiecare arc având o distanţă de valoare întreagă. = Cerință = Dându-se `N`, `M` şi cele `M` arce cu distanţele dintre ele, trebuie să calculaţi pentru Călinuţa distanţa minimă dintre fiecare două noduri. = Date de intrare = Fișierul de intrare `graph.in` conține pe prima...

2024-06-04T02:17:23Z

Pagină nouă: Călinuţa tocmai a găsit o foaie de hârtie pe care este desenat un graf orientat aciclic cu <code>N</code> noduri şi <code>M</code> arce, fiecare arc având o distanţă de valoare întreagă. = Cerință = Dându-se <code>N</code>, <code>M</code> şi cele <code>M</code> arce cu distanţele dintre ele, trebuie să calculaţi pentru Călinuţa distanţa minimă dintre fiecare două noduri. = Date de intrare = Fișierul de intrare <code>graph.in</code> conține pe prima...

New page

Călinuţa tocmai a găsit o foaie de hârtie pe care este desenat un graf orientat aciclic cu <code>N</code> noduri şi <code>M</code> arce, fiecare arc având o distanţă de valoare întreagă.

= Cerință =
Dându-se <code>N</code>, <code>M</code> şi cele <code>M</code> arce cu distanţele dintre ele, trebuie să calculaţi pentru Călinuţa distanţa minimă dintre fiecare două noduri.

= Date de intrare =
Fișierul de intrare <code>graph.in</code> conține pe prima linie numerele naturale <code>N</code> și <code>M</code> separate printr-un singur spațiu, iar pe următoarele <code>M</code> linii se află câte <code>3</code> numere <code>A</code>, <code>B</code> şi <code>C</code>, reprezentând un arc de la <code>A</code> către <code>B</code> de lungime <code>C</code>.

= Date de ieșire =
Fișierul de ieșire <code>graph.out</code> conține <code>N</code> linii cu câte <code>N</code> valori separate prin câte un spaţiu, reprezentând matricea drumurilor minime. Dacă nu există drum de la un nod <code>a</code> la un nod <code>b</code>, valoarea care trebuie afişată este <code>x</code>.

= Restricții și precizări: =

* <code>N ≤ 1500</code>
* <code>M ≤ 30.000</code>
* Numerele nodurilor sunt valori cuprinse între <code>1</code> şi <code>N</code>
* Lungimea arcelor aparţine intervalului <code>[-1000; 1000]</code>
* Pentru 25% din teste <code>N ≤ 150</code> şi <code>M ≤ 1000</code>
* Pentru alte 40% din teste <code>N ≤ 1000</code>

= Exemplu =
<code>graph.in</code>
8 9
1 2 7
2 3 -1
2 4 -2
2 7 3
8 2 -2
8 6 3
5 4 2
5 6 6
6 7 -5
<code>graph.out</code>
0 7 6 5 x x 10 x
x 0 -1 -2 x x 3 x
x x 0 x x x x x
x x x 0 x x x x
x x x 2 0 6 1 x
x x x x x 0 -5 x
x x x x x x 0 x
x -2 -3 -4 x 3 -2 0

== Rezolvare ==
<syntaxhighlight lang="python3">
def floyd_warshall(graph, N):
distances = [[float('inf')] * N for _ in range(N)]

for i in range(N):
distances[i][i] = 0

for u, v, w in graph:
distances[u - 1][v - 1] = w

for k in range(N):
for i in range(N):
for j in range(N):
if distances[i][k] != float('inf') and distances[k][j] != float('inf'):
distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])

return distances

def main():
with open("graph.in", "r") as fin:
N, M = map(int, fin.readline().split())
graph = [tuple(map(int, fin.readline().split())) for _ in range(M)]

distances = floyd_warshall(graph, N)

with open("graph.out", "w") as fout:
for row in distances:
fout.write(" ".join(map(lambda x: str(x) if x != float('inf') else "x", row)) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

0146 - graph - Revision history