Problem z teorii grafów(przeszukiwanie wszerz/głąb)

Witam, mam problem z rozwiązaniem problemu z ILOCAMP.

Autor: Jacek Tomasiewicz
W Bajtocji jest n miast. Miast są połączone jednokierunkowymi drogami. Każda droga łączy tylko dwa miast 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 będzie mógł dotrzeć z pierwszego miasta do miasta numer n.

Wyjście: n m k oznaczające kolejno liczbę miast, liczbę dróg i limit zmian
Potem m linii oznaczających połączenia między miastami
Przykładowe wejście:
5 6 1
1 2
2 3
3 4
4 5
3 1
5 2

Przykładowe wyjście:
2

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 zmiany kierunku jazdy maksymalnie k dróg.

Nie proszę o rozwiązanie a tylko o wskazówki, pierwszą moją poszlaką było aby utworzyć graf nieskierowany wyliczyć najlepszą drogę między wierzchołkami 1 i n i następnie próbować pozamieniać odpowiednio krawędzie w oryginalnym grafie skierowanym ale to jest złe rozwiązanie, dokopałem się do podpowiedzi która mówi aby utworzyć k kopii grafu a następnie w tych kopiach istnieją połączenia np między wierzchołkiem u kopii numer i a wierzchołkiem v kopii numer i+1 wtedy i tylko wtedy gdy w oryginalnym grafie istnieje krawedz v -> u.
I to wyjaśnienie robi się dla mnie o tyle niejasne, że brzmi jakbym miał łączyć ze sobą odrębne grafy.

I to wyjaśnienie robi się dla mnie o tyle niejasne, że brzmi jakbym miał łączyć ze sobą odrębne grafy.

A jaki inny pożytek byłby z robienia k kopii grafu?

Problem z teorii grafów

Problemy w teorii grafów mają nazwy. Nazwałeś temat źle, lub zbyt ogólnie.

Chodzi mi o to, że nie wiem jak łączyć te krawędzie w oddzielnych grafach.
Swoją drogą mam też problem ze zobrazowaniem sobie przebiegu algorytmu bo dla przykładowego wejścia z k = 1 robimy tylko jedną kopie a wtedy nie ma jak połączyć się z innym grafem.

Masz utworzyć k kopii grafu, więc ostatecznie masz k+1 grafów.

Oh, czyli jednak mogę łączyć też oryginalny graf z kopiami a to już robi różnicę :D