Witam, mam problem z pewnym zadaniem. Mam graf z wagami nieujemnymi dodatkowo kazdy wierzcholek ma pewna wartosc t>0. Wierzcholki sa podzielone na dwie grupy A i B. Trzeba sprawdzic czy zaistnieje sytuacja ze z jakiegos wierzcholka B dojdzie sie do wierzcholka nr 1 grupy A. Jesli dochodzimy do wierzcholka A(ktory nie jest nr 1) do idziemy dalej jedynie jesli waga krawedzi prowadzacej do miasta jest < t danego wierzcholka.
Zapewne trzeba wykorzystac tu ktorys z podstawowych algorytmow do grafow, ale kompletnie nie mam pomyslu jak wykorzystac tutaj.
Btw. Poprawilem tym razem temat ;D wtedy tez mialo byc poprawnie ale zapomnialem zmienic;) moj blad
Shalom dal rozwiazanie:
- Robimy z tego grafu graf skierowany
- Kasujemy krawędzie takie które mają wagę >= niż t w wierzchołku z którego wychodzą
- Odwracamy zwroty wszystkich krawędzi na przeciwne
- Puszczamy sobie bfs z pierwszego wierzchołka z A i rozlewamy się po grafie tak długo aż nie skończą nam się wierzchołki, albo nie trafimy na coś z B.
ale nie napisalem zasadniczej sprawy ze t i wagi grafow sa postrzegane jako czas wiec sie sumuje i podany sposob troche sie komplikuje.
Jesli idziemy np. z 4->3->1 (zakladamy ze przez pkt 3 idzie dalej )i krawedzie grafu miedzy 4-3 i 3-1 maja odpowiednio 5,6 to t wierzcholka 1 musi byc >11 aby bylo zaliczone;
Jakby miał jeszcze jakis pomysl to wielki dzieki.
ps. Shalom dzieki za zainteresowanie w poprzednim temacie