Wyszukanie najszybszej drogi

W zadaniu muszę wyznaczyć najkrótszy czas dopłynięcia nad morze lub wypisać Nie, gdy cel jest niemożliwy.

Na wejściu w pierwszej linii mam podaną ilość osad, ilość przewoźników i ilość monet. W kolejnych linijkach znajdują się informację o następnych spływach. Są to cztery liczby dodatnie, kolejno: numer osady startowej, numer osady końcowej, czas spływu i opłata.

Na wyjściu należy wypisać czas w którym można się dostać do ostatniej osady (jak najszybszy). W kolejnej linii wyjścia mają się pojawić numery kolejnych spływów potrzebnych, by osiągnąć cel.

Przykład:
Wejście
5 4 10
2 5 50 5
3 5 20 9
1 2 30 5
1 3 30 7

Wyjście
80
3 1

Jakie jest pytanie?

Nie wiem jak napisać program aby zamiast wyznaczenia spływu 1->3 wyznaczył on spływ 1->2. Ponieważ w spływie 1->3 pokonujemy od razu 2 osady w takim samie czasie jak 1->2 jedną osadę. Lecz rolę odgrywają tutaj monety. Ponieważ jak wybiorę 1->3 to już nie starczy na dopłynięcie do 5 osady.

Lekcja na dziś: algorytmy dynamiczne i problem wydawania reszty.

Tak, tylko mi chodzi o to, że jak mam wystarczającą ilość monet to żeby wybrać spływ 1->2, a nie 1->3. Jak będę mieć 10 monet to wybierze 1->3 bo w tym czasie pokonam dwie osady co w spływie 1->2 jedną osadę.

Mylisz algorytm zachłanny z dynamicznym.

Jakaś podpowiedź do tego zadania? Jak wykorzystać problem z wydawaniem reszty?

Zacznij od ZROZUMIENIA jak on działa. Szczególnie na czym polega własność optymalnej podstruktury.
Zrób tablicę w której będziesz przechowywał najlepszą drogę do danej osady. Najlepsza droga do osady k to zawsze będzie jedna z najlepszych dróg do wcześniejszych osad plus droga z tej wcześniejszej osady do k-tej (rozważamy tylko bezpośrednie połączenie!)
Załóżmy że do osady k można dopłynąć z 3 innych osad. W swojej tablicy masz już informacje o tym ile kosztuje/zajmuje dopłynięcie do tych 3 osad (bo są wcześniej na drodze i juz je policzyłeś), więc teraz tylko sprawdzasz która z opcji tablica[k-x]+spływ(k-x,k) (gdzie k-x to numer którejś z tych 3 wcześniejszych osad) jest najlepsza i tą zapisujesz sobie w tablica[k]. Postępujesz tak aż dojdziesz do końca.

Tyle, że mogę wybrać najszybszą drogę, ale może nie starczyć pieniędzy. Tak jak w przykładzie spływ 1->3 byłby lepszym wyborem, ale kosztuje aż 7 monet, więc już nie starczy na dopłynięcie do 5 osady. Nie wiem jak ten problem rozwiązać. Trzeba wybrać spływ 1->2 dlatego, że jest tańszy.

Ty w ogóle czytasz co napisałem? Bo mam wrażenie że nie. Spróbowałeś zaimplementować to co napisałem, czy cały czas snujesz jakieś idiotytczne dywagacje? o_O
tablica[0] wynosi 0 i 0 monet
tablica[1] nie jest osiągalna więc jakieś INF
tablica[2] będzie wynosiła 30 i 5 monet
tablica[3] będzie wynosiła 30 i 7 monet
tablica[4] nie jest osiągalna więc jakieś INF
tablica[5] będzie wynosiła lepsze z tablica[2]+spływ(2,5) albo tablica[3]+spływ(3,5)
więc problem o którym piszesz nie ma miejsca.

Mógłby wystąpić w innej sytuacji, bo minimalizuesz tutaj 2 parametry, więc moja rada to zapamiętywać dwa "najlepsze" rozwiązania w każdym węźle -> jedno ze względu na czas a drugie ze względu na monety. Tzn jeśli masz potencjalne dwa najlepsze rozwiązania, z których jedno jest krósze a drugie mniej kosztowne to zapamiętujesz oba.

W przypadku gdy spływów którymi dotrze się do ostatniej wioski będzie więcej niż dwa to w tablicy[5] mają być przechowane wszystkie dotychczasowe najlepsze spływy?

Tylko na jakiej podstawie określać najlepszą drogę do danej osady? Można podzielić ile osad przepłyniemy przez czas otrzymując średni czas na jedną osadę. Lecz jak uporać się z tymi monetami?