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 muchii.
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 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.
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
- ... ≤ ... ≤ ...
Exemplu
| dijkstra.in | dijkstra.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
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
...
