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 ≤ 100 000
- Lungimile arcelor sunt numere naturale cel mult egale cu 1000.
- 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.
O rezolvare in O(NlogN) folosind un heap obtine 100 de puncte. O descriere a acestei structuri de date puteti gasi tot pe wikipedia
...
