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

Se da un graf orientat si ponderat cu N noduri si M muchii.

Se da un graf orientat si ponderat cu $N$ noduri si $M$ muchii.

h2. Cerinta

Sa se determine lungimea minima a drumului de la nodul 1 la fiecare din nodurile 2, 3, ..., N-1, N si sa se afiseze aceste distante. Lungimea unui drum este data de suma lungimilor arcelor care constituie drumul.

Sa se determine lungimea minima a drumului de la nodul $1$ la fiecare din nodurile $2$, $3$, ..., $N-1$, $N$ si sa se afiseze aceste lungimi. Lungimea unui drum este data de suma lungimilor arcelor care constituie drumul.

h2. Date de intrare

Fisierul de intrare $dijkstra.in$ ...

Fisierul de intrare $dijkstra.in$ contine pe prime linie numerele $N$ si $M$, separate printr-un spatiu, cu semnificatia din enunt. Urmatoarele $M$ linii contin, fiecare, cate 3 numere naturale separate printr-un spatiu $A$ $B$ $C$ semnificand existenta unui arc de lungime $C$ de la nodul $A$ la nodul $B$.

h2. Date de iesire

In fisierul de iesire $dijkstra.out$ ...

In fisierul de iesire $dijkstra.out$ veti afisa pe prima linie $N-1$ numere naturale separate printr-un spatiu. Al $i$-lea numar va reprezenta  lungimea unui drum minim de la nodul $1$ la nodul $i+1$.

h2. Restrictii

  multiple lines.
|

h3. Explicatie

h3. Indicatii de rezolvare
 
Exista o descriere a algoritmului pe 'wikipedia':http://en.wikipedia.org/wiki/Dijkstra's_algorithm
 
O rezolvare in O(N^2^) obtine 40 de puncte.
O rezolvare in O(NlogN) folosind un heap obtine 100 de puncte. O descriere a acestei structuri de date puteti gasi tot pe 'wikipedia':http://en.wikipedia.org/wiki/Binary_heap

...