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

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

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

h2. Cerinta

h2. Restrictii
* $1 ≤ N ≤ 50 000$

* $1 ≤ M ≤ 250 000$
* Lungimile arcelor sunt numere naturale cel mult egale cu $20 000$.
* Pot exista arce de lungime $0$

* Lungimile arcelor sunt numere naturale cel mult egale cu $1 000$.

* Nu exista un arc de la un nod la acelasi nod.
* Daca nu exista drum de la nodul $1$ la un nod $i$, se considera ca lungimea minima este $0$.
* Arcele date in fisierul de intrare nu se repeta.

|1 3 2 5
|

h2. Indicatii de rezolvare
Exista o descriere a algoritmului pe 'wikipedia':http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm.

h3. Indicatii de rezolvare

O rezolvare de complexitate {$O(N^2^)$} obtine $40$ de puncte si se poate gasi 'aici':job_detail/144256?action=view-source.
O rezolvare in {$O(MlogN)$} folosind un heap obtine $100$ de puncte si se poate gasi 'aici':job_detail/144766?action=view-source. O descriere a acestei structuri de date puteti gasi tot pe 'wikipedia':http://en.wikipedia.org/wiki/Binary_heap. O implementare de aceeasi complexitate foloseste in loc de heap structura de date numita SET, care este de fapt un arbore binar echilibrat si permite interogarea costului minim si modificarea costurilor in timp logaritmic. Aceasta abordare se gaseste 'aici':job_detail/1788038 si are avantajul ca necesita un cod mult mai scurt. Totusi, ea este mai inceata decat solutia cu heap-uri.
O alta rezolvare utila in concursuri este algoritmul 'Bellman-Ford':http://en.wikipedia.org/wiki/Bellman-Ford_algorithm cu coada. Aceasta solutie are complexitatea teoretica {$O(N*M)$}, in practica 'solutia':job_detail/1788046?action=view-source se dovedeste destul de rapida pe teste generate la intamplare, dar exista teste pe care atinge timpi foarte mari, obtinand un scor de 90 de puncte.

Exista o descriere a algoritmului pe 'wikipedia':http://en.wikipedia.org/wiki/Dijkstra's_algorithm

h2. Probleme asemanatoare

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 *Feedback(Silviu)*: Vom finaliza 'articolul':heapuri despre heapuri in curand. De asemenea Dijkstra se poate implementa si cu Arbori de intervale sau set-uri STL. Sper sa avem in viitorul apropiat un articol despre Dijkstra in care sa fie explicate abordarile astea :)

* 'Base3':problema/base3
* 'Distante':problema/distante
* 'Catun':problema/catun
* 'Runaway':http://acm.sgu.ru/problem.php?contest=0&problem=240
* 'Sightseeing trip':http://acm.pku.edu.cn/JudgeOnline/problem?id=1734

*Feedback(Cosmin)*: Complexitatea algoritmului lui Dijkstra e O(m log n) folosind un heap si O(n log n + m) folosind un heap Fibonacci, nu e O(NlogN) cum ai zis acolo.

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

h3. Probleme asemanatoare
 
* 'Distante':http://infoarena.ro/problema/distante
* 'Catun':http://infoarena.ro/problema/catun
!!!Problema nu este inca finalizata, s-ar putea sa se fi strecurat niste greseli in teste, mai trebuie sa fac niste verificari.
== include(page="template/taskfooter" task_id="dijkstra") ==

2778