Олимпиада проводится при поддержке Московского физико-технического института, Благотворительного фонда "Династия", компьютерной компании НИКС, Компании Yandex, компании Genius
Информационная поддержка:
журнал "Мир ПК"
III Всероссийская заочная олимпиада школьников по информатике, 2008/09 учебный год
Задача E. Ездящий город (on+off-line проверка, максимальная оценка - 150 баллов)
| Имя входного файла: | e.in |
| Имя выходного файла: | e.out |
| Максимальное время работы на одном тесте: | 2 секунды |
| Максимальный объем используемой памяти: | 64 мегабайта |
Мосгортранс в честь дня своего рождения решил провести соревнования, и, по аналогии с "Бегущим городом" назвать их "Ездящий город".
Участник соревнований получает маршрутный лист, где указано, какие контрольные пункты и в каком порядке он должен посетить (в каждом пункте участник должен отметиться). При этом участник должен отмечаться в пунктах строго в указанном порядке. Какие-то пункты может потребоваться посетить несколько раз.
Специально по случаю соревнования между контрольными пунктами будут ходить автобусы. Перемещаться от контрольного пункта к контрольному пункту разрешается только на автобусах. При этом можно пользоваться как прямым рейсом, соединяющим контрольные пункты (если он существует), так и добираться с пересадкой через другие контрольные пункты (если это оказывается быстрее или если прямого маршрута вовсе нет), при этом в пересадочных пунктах участник не отмечается.
Известен маршрутный лист участника и расписание движения автобусов. Требуется определить минимальное время, которое понадобится участнику на прохождение маршрута.
Формат входных данных
Сначала вводится число N - общее количество контрольных пунктов (2≤N≤10000).
Далее вводится количество автобусных маршрутов K (1≤K≤50000). Далее идет K описаний автобусных маршрутов.
Каждый маршрут описывается четырьмя числами Ai, Bi, Ci, Di, которые означают, что каждые Ci минут (т.е. в моменты времени 0, Ci, 2*Ci, ...) автобус выходит от контрольного пункта Ai и через Di минут прибывает к контрольному пункту Bi. Все Ci и Di - натуральные и не превышают 10000.
Будем считать, что времени на то, чтобы отметиться на контрольном пункте и на то, чтобы пересесть с автобуса на автобус, участнику не требуется. Т.е. если, например, в момент 10 он прибывает на какой-то контрольный пункт, то дальше он может уехать любым автобусом, отправляющимся от этого контрольного пункта в момент времени 10 или позднее.
Далее вводится число M - количество контрольных пунктов в маршрутном листе участника (2≤M≤50). Далее вводятся M чисел P1, P2, ..., PM - номера контрольных пунктов, которые нужно посетить (числа в этом списке могут повторяться). В момент времени 0 участник находится в пункте P1. Временем прохождения маршрута считается момент времени, когда участник окажется в пункте PM.
Формат выходных данных
Выведите одно число - минимальное время, за которое участник может пройти маршрут. Если существующие автобусные рейсы не позволяют пройти маршрут, выведите одно число -1 (минус один).
Примеры
| e.in | e.out |
2 2 2 1 3 1 1 2 5 4 3 1 2 1 |
7 |
3 4 2 1 30 10 1 2 50 40 2 3 45 10 3 1 55 10 3 1 2 1 |
65 |
2 2 1 2 3 1 1 2 5 4 3 1 2 1 |
-1 |