Cu Dijkstra cum se poate face?
Poti determina cu Dijkstra asa cum a spus Cotizo: odata gasita distanta minima pana la fiecare nod, DAG-ul drumurilor minime va fi format din toate muchiile (u,v) pentru care dist[ u ] + cost(u,v) = dist[ v ].
Apoi, din cate am inteles din citatul tau, ai deja un arbore (graf) pe muchiile caruia daca mergi, ajungi in cost minim de la sursa la orice nod
Din cate am inteles eu, e un fel de labirint in care sa treci dintr-o celula in alta ai cost 1, si sa spargi un zid ai cost p. Deci nu poti face o parcurgere in graful original pentru a gasi un drum minim. Intr-adevar, dupa ce ai obtinut DAG-ul drumurilor minime, faci o parcurgere si cauti drumul cu cat mai putine muchii de cost p.