== include(page="template/taskheader" task_id="dijkstra") ==
Poveste si cerinta...
Se da un graf orientat cu $N$ noduri si $M$ arce.
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 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 prima 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
* $... ≤ ... ≤ ...$
* $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$
* 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.
h2. Exemplu
table(example). |_. dijkstra.in |_. dijkstra.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|5 6
1 2 1
1 4 2
4 3 4
2 3 2
4 5 3
3 5 6
|1 3 2 5
|
h2. Indicatii de rezolvare
Exista o descriere a algoritmului pe 'wikipedia':http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm.
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.
h2. Probleme asemanatoare
* '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
h3. Explicatie
== include(page="template/taskfooter" task_id="dijkstra") ==
...
== include(page="template/taskfooter" task_id="dijkstra") ==
