Трамваи города S
Задачу добавил: alef
Успешно сдано решений: 3
Гости города S решили навестить своего друга. Они знают, что его дом находится возле трамвайной остановки.У гостей города S есть карта, на которой указаны все трамвайные пути и остановки, а также трамвайные маршруты. Один из гостей города S составил список из номеров трамваев и остановок, на которых нужно выходить, чтобы пересесть на следующий трамвай.
Ваша задача - по карте и списку определить время, за которое гости города S смогут добраться до дома своего друга. Если сделать это невозможно (список мог быть составлен с ошибками), выведите в качестве ответа -1.
Формат входного файла input.txt
Первая строка - целые числа N, M, A, B, S через пробел, где
N - число остановок (будем полагать их занумерованными числами от 1 до N) (2 <= N <= 500)
M - количество трамвайных маршрутов (1 <= M <= 300)
A - номер остановки возле гостиницы (точка отправления гостей города) (1 <= A <= N). Гости города S приходят на нее в момент времени, равный 0.
B - номер остановки возле дома друга гостей города (1 <= B <= N, B <> A)
S - количество строк в списке гостя города (1 <= S <= 300)
Далее следуют M групп по 3 строки, описывающие трамвайные маршруты.
Первая строка описания содержит три целых числа Qj, Cj и Dj (j = 1, 2, ... M) через пробел, где
Qj - количество остановок в маршруте #j (2 <= Qj <= N)
Cj (Cj >= 0) - время появления первого трамвая данного маршрута на первой остановке маршрута. Время отсчитывается от момента появления на остановке #А гостей города S.
Dj (Dj >= 0) - интервал времени (в минутах), через который трамваи этого маршрута отправляются с начальной остановки. Если Dj = 0, это означает, что трамвай выходит на маршрут единожды.
Вторая строка описания содержит последовательность остановок маршрута - Qj целых чисел P1j, P2j, ..., PQjj через пробел (Pk j <> Pk+1 j).
Третья строка содержит Qj-1 целое число: U12j, U23j, U34j, ..., UQj-1Qjj - интервалы времени (в минутах), за которые трамвай доезжает от одной остановки до другой (от первой до второй, от второй до третьей и т.д.)
Каждая из следующих S строк содержит по два целых числа Ti и Ki (i = 1, 2, ... S) через пробел, где
Ti (1 <= Ti <= M) - номер трамвая, на который следует сесть гостям города на "текущей остановке"
Ki (1 <= Ki <= N) - номер остановки, на которой им следует выйти
Для первого трамвая в списке текущей считается остановка #A, для каждого последующего - та остановка, на которой гости города вышли из предыдущего трамвая.
Пересадка с трамвая на трамвай не может происходить мгновенно. Если гости города вышли из трамвая на некоторой остановке в момент времени t, то сесть в следующий трамвай они могут только в момент времени t+1 (т.е. если трамваи оказались на остановке одновременно, пересесть из одного в другой не удастся).
Гарантируется, что гости города потратят не более 10^6 минут, чтобы добраться до дома своего друга, если это возможно.
Формат выходного файла output.txt
Первая строка содержит одно целое число - время в минутах, за которое гости города S доберутся от остановки A до остановки B. Если это невозможно сделать, выведите -1.
Пример входного файла
6 2 1 6 2
4 1 15
1 2 3 4
4 5 3
3 2 10
5 3 6
5 6
1 3
2 6
Пример выходного файла:
23