Mam takie zadanie:
Autobus
Limit pamięci: 32 MB
W związku z nadchodzącymi wyborami, władze Bajtogrodu postanowiły uruchomić nową linię autobusową.
W Bajtogrodzie jest skrzyżowań oraz jednokierunkowych ulic łączących te skrzyżowania. Każda ulica ma kształt odcinka łączącego dwa skrzyżowania (nie ma na niej żadnych łuków, skrętów itd.). Skrzyżowania to jedyne miejsca, gdzie można zjechać z ulicy na inną - jeśli dwie ulice się krzyżują, a nie ma tam skrzyżowania, to prawdopodobnie jedna prowadzi tunelem albo wiaduktem; jeśli natomiast dwie ulice się pokrywają, to prawdopodobnie jedna prowadzi estakadą. Dwa skrzyżowania mogą być połączone przez wiele dróg - takie drogi uważane są wówczas za różne.
Prace posuwały się na początku szybko - bez problemu ustalono, jaki jest czas przejazdu autobusu przez każdą ulicę (okazało się, że wartość ta wyrażała się dla każdej ulicy parzystą liczbą minut), na których ulicach trzeba ustawić przystanki (przystanek zawsze stoi dokładnie w połowie ulicy, czyli od początku ulicy do przystanku autobus jedzie tak samo długo, jak od przystanku do końca ulicy) oraz w jakiej kolejności autobus ma je odwiedzać.
Dalej jednak zaczęły się schody.
Po pierwsze, okazało się, że autobus jest mało zwrotny, i może na skrzyżowaniach wykonywać skręty tylko wtedy, kiedy kąt skrętu jest nie większy niż .
Jeżeli autobus jedzie w kierunku zgodnym ze strzałką, to oznacza jego kąt skrętu.
Po drugie, nikt w Bajtogrodzkim Urzędzie Miasta nie potrafi znaleźć optymalnej trasy dla autobusu, minimalizującej czas przejazdu autobusu z pierwszego do ostatniego przystanku. Twój przyjaciel, który pracuje w Urzędzie, poprosił Cię o pomoc. Pomóż mu ułożyć optymalną trasę! Możemy przyjąć, że autobus w ogóle się nie zatrzymuje na przystankach (z dodaniem czasu na postój urzędnicy już sobie poradzą), lecz wystarczy, jeżeli przejedzie koło każdego z nich.
Zadanie
Napisz program, który:
wczyta ze standardowego wejścia opis Bajtogrodu oraz zamierzonych przystanków,
wyznaczy optymalną trasę autobusu,
wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz wejścia zawiera trzy liczby całkowite n, m i p (3 <= n <= 50, 2 <= m <= 500 ,2 <= p <= 100 ), pooddzielane pojedynczymi odstępami - liczbę skrzyżowań w Bajtogrodzie, liczbę ulic i liczbę zamierzonych przystanków.
Kolejne n wierszy opisuje skrzyżowania. W i-szym wierszu wejścia znajdują się dwie liczby całkowite x i y (-10 000 <= x, y <= 10 000), oddzielone pojedynczym odstępem - współrzędne i-tego skrzyżowania. Skrzyżowania są ponumerowane 1 od do n.
Następne m wierszy zawiera informacje o kolejnych ulicach. W n+ i + 1 -szym wierszu znajdują się trzy liczby całkowite - a, b t oraz (1 <= a,b<=n, a != b, 1 <= t <= 5 000), pooddzielane pojedynczymi odstępami. Oznaczają one, że i-ta ulica prowadzi ze skrzyżowania a do b i czas przejazdu po tej ulicy wynosi 2 * t . Ulice są ponumerowane od 1 do m.
W kolejnych p wierszach znajduje się po jednej liczbie całkowitej; w wierszu n + m + i + 1-szym znajduje się e (1 <= e <= m) - numer ulicy, przy której ma się znaleźć i-ty przystanek. Numery ulic mogą się powtarzać - jeśli ei = ej, to oznacza, że po odwiedzeniu przystanków na ulicach e1...e2...ei...ej-1 autobus ma wrócić na przystanek przy ulicy ej. W szczególności, jeżeli ei = ei+1, to autobus powinien odjechać z przystanku ei, a następnie wrócić do niego.
Wyjście
Jeśli nie istnieje trasa spełniająca wymogi Urzędu, to należy wypisać tylko jedno słowo NIE. W przeciwnym przypadku należy wypisać wierszy. W i-tym wierszu powinien się znaleźć czas przyjazdu autobusu na i + 1-szy przystanek (licząc od odjazdu z przystanku pierwszego), przy założeniu, że autobus jedzie optymalną trasą.
Przykład
Dla danych wejściowych:
4 6 3
-1 -1
1 -1
1 1
-1 1
1 2 1
2 3 2
3 4 3
4 1 5
2 4 1
1 3 2
1
4
3
poprawną odpowiedzią jest:
16
30
Moglibyście doradzić jakiego algorytmu powinienem użyć w tym zadaniu ?
LINK DO ZADANIA