Mam takie zadanie:
W Bajtocji jest n miast. Miasta są połączone jednokierunkowymi drogami. Każda droga łączy tylko dwa miasta i nie przechodzi przez żadne inne. Król Bajtazar chce się dostać z pierwszego miasta do n-tego, przemieszczając się jak najmniejszą liczbą dróg. Postanowił, że w dzień jego wyprawy może zostać zmieniony kierunek jazdy niektórych dróg, jednak ze względów praktycznych liczba dróg, w których kierunek się zmieni, nie może przekroczyć k. Król musi przygotować się do podróży, więc wybór dróg do zmiany kierunku jazdy powierzył Tobie. Możesz założyć, że przy obecnych kierunkach dróg król będzie mógł dotrzeć z pierwszego miasta do miasta numer n.
Wejście Pierwszy wiersz wejścia zawiera trzy liczby całkowite n, m oraz k (2 <= n <= 10 000, 1 <= m <= 100 000, 0 <= k <= 50) oznaczające, odpowiednio, liczbę miast, liczbę dróg w Bajtocji oraz liczbę dróg, dla których można zmienić kierunek jazdy. Miasta są ponumerowane liczbami od 1 do n. W kolejnych m wierszach znajdują się po dwie liczby całkowite. W i-tym z nich są liczby ai i bi (1 <= ai , bi <= n) reprezentujące jednokierunkową drogę prowadzącą z miasta ai do miasta bi
Wyjście Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą równą minimalnej liczbie dróg, jakie Bajtazar musi przejechać, aby dostać się z miasta numer 1 do miasta numer n, z uwzględnieniem możliwości zmian kierunku jazdy maksymalnie k dróg.
Przykład
Dla danych:
5 6 1
1 2
2 3
3 4
4 5
3 1
5 2
Poprawna odpowiedź to:
2
Wyjaśnienie: Bajtazar pojedzie drogą od 1 do 2 zgodnie z kierunkiem jazdy, a następnie drogą od 2 do 5, dla której został zmieniony kierunek jazdy.
No i mam taką odpowiedź:
Zadanie możemy rozwiązać w czasie O(k · (n + m)).
• Tworzymy k kopii grafu. W ramach każdej kopii krawędzie są takie jak w oryginalnym grafie, a z wierzchołka u w kopii i do wierzchołka v w kopii i + 1 jest krawędź wtedy i tylko wtedy, gdy w oryginalnym grafie jest krawędź v → u. Na końcu znajdujemy minimalną odległość do wierzchołka docelowego w dowolnej kopii.
Nie rozumiem tego rozwiązania przecież robiąc k kopii dla przykładu testowego (czyli 1) otrzymalibyśmy coś takiego
Pomoże mi ktoś zrozumieć jak zrobić to zadanie?
