== include(page="template/taskheader" task_id="royfloyd") ==

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

Se da un graf orientat cu $N$ noduri, memorat prin matricea ponderilor.

h2. Cerinta

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

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 (al $j$-lea numar de pe linia $i+1$ reprezinta costul muchiei de la $i$ la $j$ din graf, sau {$0$}, in cazul in care intre cele doua noduri nu exista muchie).

h2. Date de iesire

* $1 ≤ N ≤ 100$
* Numerele din fisierul de intrare nu vor depasi valoarea $1 000$.

* Daca nu exista muchie intre o pereche de noduri $x$ si $y$, distanta de la nodul $x$ la nodul $y$ din fisierul de intrare va fi 0.
* Daca dupa aplicarea algoritmului nu se gaseste un drum intre o pereche de noduri $x$ si $y$, se va considera ca distanta intre cele doua noduri este 0.
* Nu exista drum intre un nod la el insusi ( $a{~i,i~}$ este $0$ pentru orice $i$ cuprins intre $1$ si $N$).

h2. Exemplu

4 7 3 2 0
|

h3. Indicatii de rezolvare

h2. Indicatii de rezolvare
 
Algoritmul are complexitatea O(N^3) si este explicat atat pe 'wikipedia':http://en.wikipedia.org/wiki/Floyd-Warshall cat si in cartea _Introducere in algoritmi_, Thomas Cormen, editura Agora, Cluj-Napoca. Sursa de 100 de puncte se gaseste 'aici':/infoarena.ro/job_detail/143352?action=view-source .
 
Ca exercitiu pentru a vedea daca ati inteles algoritmul, explicati de ce nu merge sa se schimbe ordinea forurilor, de exemplu sa fie forurile in ordinea i, j, k in loc de k, i, j, iar conditia interioara sa fie aceeasi.
 
h2. Probleme suplimentare

Algoritmul are complexitatea O(N^3) si este explicat atat pe 'wikipedia':http://en.wikipedia.org/wiki/Floyd-Warshall cat si in cartea _Introducere in algoritmi_, Thomas Cormen, editura Agora, Cluj-Napoca. Sursa de 100 de puncte se gaseste 'aici':/job_detail/143213?action=view-source .

Alte probleme care se rezolva cu Algoritmul Floyd-Warshall/Roy-Floyd :
 
* 'Roy-Floyd':problema/rf
* 'Rfinv':problema/rfinv
* 'Coach':problema/coach

== include(page="template/taskfooter" task_id="royfloyd") ==

2764