Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

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

Ostatnio zmodyfikowano 2018-07-01 12:42
Autor Wiadomość
Mati3k01
Temat założony przez niniejszego użytkownika
Problem z teorii grafów(przeszukiwanie wszerz/głąb)
» 2018-06-26 15:39:08
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.
P-171701
pekfos
» 2018-06-26 15:46:06
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.
P-171702
Mati3k01
Temat założony przez niniejszego użytkownika
» 2018-06-30 09:59:15
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.
P-171720
pekfos
» 2018-06-30 13:42:47
Masz utworzyć k kopii grafu, więc ostatecznie masz k+1 grafów.
P-171725
Mati3k01
Temat założony przez niniejszego użytkownika
» 2018-07-01 12:42:01
Oh, czyli jednak mogę łączyć też oryginalny graf z kopiami a to już robi różnicę :D
P-171732
« 1 »
  Strona 1 z 1