Wyznaczenie najkrótszej ścieżki.

[acichon89]

Cześć, na początku zaznaczę, że nie szukam rozwiązania problemu, a raczej zdefiniowania go. Policzyć będę umiał już sam

AU

gra.png (14.01 KiB) Przejrzano 78 razy

Kod: Zaznacz cały

https://i.ibb.co/Msphp4v/gra.png

Mam taką grę. Jest grupa zwierząt, każda ma do pokonania dystans w 7 rundach. Koszt przeskoczenia do kolejnej rundy dla każdego zwierzaka jest znany. Zadanie polega na wytypowaniu dwójki zwierząt, na których możemy "podróżować". I tak np. wybieram psa i kota. W pierwszej rundzie jadę na psie i kosztuje mnie to 2 pkt. W drugiej punkcie zamieniam na kota i zamiast "psich" 4 pkt jadę dalej za 2 pkt. W czasie podróży przez rundy mogę podmienić jednego zwierzaka na niewybranego (np. psa na jeża) i wtedy mogę wybierać pomiędzy parą jeż-kot.

Generalnie trzeba wyznaczyć parę zwierząt na starcie i maksymalnie 2 podmiany (ewentualne) w trakcie wyscigu, dzięki którym najtaniej przejdziemy 7 rund.

Bez podmian raz wybranej pary na początku wyścigu jest dla mnie to łatwe, zwykły algorytm dijkstry i zamienienie planszy na graf. Ale w przypadku uwzględnienia możliwej zamiany wybranych zwierząt jestem w kropce, nie wiem jak do tego podejść.