Ktoś się pochwali zgrabnym kodem tegoż zadania? Bo moje rozwiązanie było strasznie obszerne. Najpierw tworzyłem DAG (directed acyclic graph) z wyciągów, i obliczałem standardowo liczbę ścierzek z każdego punktu gdzie zaczyna się wyciąg do każdego punktu gdzie kończy się wyciąg, czyli tabelka K*K = 300*300, następnie z każdego punktu gdzie kończy się wyciąg na mapie ten sam algorytm wyliczania liczby ścierzek do wszystkich punktów na mapce czyli K*N*M potem to ładnie wymnażałem dla każdej pary punktów gdzie zaczyna się i kończy wyciąg i sumowałem wszystko do wyniku.
Udało się 10/10.
Czas ostatnich testach 29 82 102 ms.
Ktoś miał jakieś inne rozwiązania?

Dokładnie tak samo chciałem robić, tylko nie wiem jak się szuka ilości ścieżek. Mógłbyś powiedzieć jakiego "standardowego" algorytmu użyłeś?

btw, ścieżek, aż oczy bolą

Jeśli o mnie chodzi to najpierw generowałem wszystkie możliwe wyciągi (tzn pkt. do których mogłem dostać się różnymi wyciągami, tu możliwe, że zrobiłem błąd) po czym dla każdej możliwości rekurencyjnie spr. ilość dróg powrotnych do pkt z którego wyruszyłem. Niestety prawdopodobnie generowanie źle napisałem przez co mam tylko 1 pkt

@up nie musisz znać ilości ścieżek, musisz znać dla każdej pkt startu i punkt końcowy Przynajmniej w moim rozumowaniu, możliwe, że @Michał miał inny koncept (lub Ty).

No jak mamy dag to możemy wierzchołki posortować topologicznie, ustawiamy ilość ścieżek dla pierwszego wierzchołka na 1 i idziemy przez wszystkie wierzchołki (np BFS) aktualizując liczbę ścieżek : d[v] += d[u]

To tak w skrócie

Można też zapuścić DFSa na transponowanym grafie, który dynamicznie aktualizuje ilość ścieżek.