Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-02-26 09:19:35.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:royfloyd.in, royfloyd.outSursăad-hoc
AutorArhiva EducationalaAdăugată degabitzish1Gabriel Bitis gabitzish1
Timp execuţie pe test0.025 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Floyd-Warshall/Roy-Floyd

Fiind dat un graf orientat cu N noduri, memorat prin matricea prin matricea ponderilor.

Cerinta

Sa se determine pentru orice pereche de noduri x si y lungimea minima a drumului de la nodul x la nodul y si sa se afiseze matricea drumurilor minime. Prin lungimea unui drum intelegem suma costurilor arcelor care-l alcatuiesc.

Date de intrare

Fisierul de intrare royfloyd.in contine pe prima linie N, numarul de noduri al grafului, iar urmatoarele N linii contin cate N valori reprezentand matricea ponderilor.

Date de iesire

In fisierul de iesire royfloyd.out se vor afisa N linii a cate N valori, reprezentand matricea drumurilor minime.

Restrictii

  • 1 ≤ N ≤ 100
  • Numerele din fisierul de intrare nu vor depasi valoarea 1000.

Exemplu

royfloyd.inroyfloyd.out
5
0 3 9 8 3
5 0 1 4 2
6 6 0 4 5
2 9 2 0 7
7 9 3 2 0
0 3 4 5 3
5 0 1 4 2
6 6 0 4 5
2 5 2 0 5
4 7 3 2 0

Indicatii de rezolvare

Algoritmul are complexitatea O(N^3) si este explicat atat pe wikipedia cat si in cartea Introducere in algoritmi, Thomas Cormen, editura Agora, Cluj-Napoca. Sursa de 100 de puncte se gaseste aici .

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?