[SMWP_117] Niebezpieczna Droga

0 Flares Twitter 0 Facebook 0 0 Flares ×

Link do zadania:
http://www.spoj.com/SMWP/problems/SMWP_117/

Opis problemu:
Celem naszego zadania jest znalezienie takiej drogi dla Jasia z domu do szkoły, aby bohater przeszedł przez najmniejszą liczbę skrzyżowań oraz przy tym w jak najkrótszym czasie. Następnie dla wyznaczonej drogi musimy policzyć czas jej przebycia i odjąć uzyskaną sumę minut od godziny 10:00, czyli zakończenia roku szkolnego. Przyjmujemy, że czasy wchodzenia/wychodzenia do/z budynków jest pomijalnie mały. Ponadto czas zawiera się w tym samym dniu, więc maksymalny czas dojścia do szkoły to 600 minut.

Rozwiązanie:
Jednym z rozwiązań jest zastosowanie algorytmu opierającego się na przeszukiwaniu wszerz grafu wagowego. Metodą BFS odwiedzani są najpierw wszyscy sąsiedzi wierzchołka startowego, a następnie zostają odwiedzeni wszyscy sąsiedzi tych sąsiadów. Jednocześnie podczas przechodzenia grafu aktualizujemy w odpowiedni sposób dla każdego wierzchołka odległości od wierzchołka startowego. Mianowicie musimy pamiętać o tym, że na przykład połączenie 1-3 o koszcie 1000 jest „tańsze” od dwóch połączeń 1-2-3 o koszcie łącznym 2. Zatem nasze odległości są aktualizowane tylko wtedy, gdy docieramy do danego wierzchołka po raz pierwszy lub gdy liczba wierzchołków składająca się na obecny wynik jest równa aktualnej liczbie wierzchołków na rozpatrywanej ścieżce i przy tym bardziej opłacalna czasowo. Tym samym nie wyznaczamy co prawda minimalnego kosztu dojścia pomiędzy domem a szkołą, ale za to BFS’em wyznaczamy ścieżkę złożoną z najmniejszej ilości wierzchołków,a więc jest to szukana minimalna liczba skrzyżowań do pokonania przez Jasia. Aktualizowanie odległości od startu ponadto pomaga nam wybrać najszybszą drogę wśród określonych już dróg o minimalnej liczbie skrzyżowań.

Print Friendly

Dodaj komentarz

Wymagane pola są oznaczone *.