Gazdaságos tankolás - megoldás
Algoritmus
Az adatszerkezet kitalálása nehéz. Vegyük azt a gráfot, amelynek csúcsai
(város,liter) párok. A csúcsok azt jelentik, hogy az adott városban vagyunk,
ennyi liter benzinnel a tankunkban.
Két csúcs között két esetben vezet él.
-
(v,l)--(v,l+1): a v városban tankoltunk egy litert.
(l+1 nem több, mint az autó kapacitása.)
Az ilyen élek "hossza"
a v városban érvényes benzinár.
-
(v,l)--(v',l-d): a v és v' városok távolsága d, és
l legalább d.
Az ilyen élek "hossza" 0.
A fenti módon definiált gráfon egy legrövidebb út problémát kell megoldanunk, ez
Dijkstra algoritmusával megy. A célpontot reprezentáló csúcsok közül az érdekes,
amelyet a legolcsóbban értünk el.
(Az (e,0),(e,1),(e,2),...,(e,kapacitás) csúcsok bármelyikébe
érkezhetünk.)
Kód
