Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | dijkstra.in, dijkstra.out | Sursă | ad-hoc |
| Autor | Arhiva Educationala | Adăugată de |  Ionescu Vlad •Dastas |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Algoritmul lui Dijkstra
Se da un graf orientat si ponderat cu N noduri si M arce.
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.
Date de intrare
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.
Date de iesire
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.
Restrictii
- 1 ≤ N ≤ 50 000
- 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.
Exemplu
| dijkstra.in | dijkstra.out |
|---|---|
| 5 6 1 2 1 1 4 2 4 3 4 2 3 2 4 5 3 3 5 6 | 1 3 2 5 |
Indicatii de rezolvare
Exista o descriere a algoritmului pe wikipedia's_algorithm
O rezolvare in O(N2) obtine 40 de puncte si se poate gasi aici.
O rezolvare in O(M log N) folosind un heap obtine 100 de puncte si se poate gasi aici. O descriere a acestei structuri de date puteti gasi tot pe wikipedia Feedback(Silviu): Vom finaliza articolul 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 :)
Cosmin: am modificat, mersi.
Probleme asemanatoare
!!!Problema nu este inca finalizata, s-ar putea sa se fi strecurat niste greseli in teste, mai trebuie sa fac niste verificari.
