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 
, 
i 
(
, 
, 
), pooddzielane pojedynczymi odstępami - liczbę skrzyżowań w Bajtogrodzie, liczbę ulic i liczbę zamierzonych przystanków.
Kolejne 
wierszy opisuje skrzyżowania. W 
-szym wierszu wejścia znajdują się dwie liczby całkowite 
i 
(
), oddzielone pojedynczym odstępem - współrzędne 
-tego skrzyżowania. Skrzyżowania są ponumerowane od 
do 
.
Następne 
wierszy zawiera informacje o kolejnych ulicach. W 
-szym wierszu znajdują się trzy liczby całkowite - 
, 
oraz 
(
, 
, 
), pooddzielane pojedynczymi odstępami. Oznaczają one, że 
-ta ulica prowadzi ze skrzyżowania 
do 
i czas przejazdu po tej ulicy wynosi 
. Ulice są ponumerowane od 
do 
.
W kolejnych 
wierszach znajduje się po jednej liczbie całkowitej; w wierszu 
-szym znajduje się 
(
) - numer ulicy, przy której ma się znaleźć 
-ty przystanek. Numery ulic mogą się powtarzać - jeśli 
, to oznacza, że po odwiedzeniu przystanków na ulicach 
autobus ma wrócić na przystanek przy ulicy 
. W szczególności, jeżeli 
, to autobus powinien odjechać z przystanku 
, 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 
-tym wierszu powinien się znaleźć czas przyjazdu autobusu na 
-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
Na rysunku kółkami oznaczono skrzyżowania, a kwadratami - przystanki. Cienkimi kreskami oznaczono ulice, natomiast grubą - najlepszą możliwą trasę z pierwszego przystanku na drugi, czyli pierwszy fragment optymalnej trasy autobusu. Dla uproszczenia na rysunku pominięto czasy przejazdu przez poszczególne ulice.
Nie wiem za bardzo jak się za to zabrać pomoże ktoś?
