ТРОЛЕЙБУСНІ МАРШРУТИ
ТРОЛЕЙБУСНІ МАРШРУТИ
Микола приїхав на обласну олімпіаду з інформатики. Вийшовши з вокзалу, зрозумів, що запізнюється на початок туру. Микола вирішив якомога швидше доїхати до місця проведення олімпіади, скориставшись тим, що проїзд у тролейбусах міста для учасників олімпіади безкоштовний.
Відомо, що у місті існує N зупинок, які обслуговуються K тролейбусними маршрутами.
Відомі маршрути руху тролейбусів та кількість хвилин, які займає кожний переїзд між зупинками маршруту.
Початкова та кінцеві зупинки тролейбусів одного маршруту завжди різні, тобто маршрути не замкнені.
В нульовий момент часу (t = 0)
з усіх кінцевих зупинок виїжджають тролейбуси. При цьому на кожному маршруті з кінцевих зупинок вирушають назустріч одному два тролейбуси. Коли тролейбус приїжджає на кінцеву зупинку, одразу ж з цієї зупинки вирушає тролейбус у зворотному напрямі.
Микола знаходиться на зупинці А
і повинен дістатися до зупинки В
.
При цьому він може виходити з тролейбуса і пересідати на інший. У цьому випадку йому, можливо, доведеться чекати його. Час стоянки тролейбусу, висадки і посадки вважаємо рівними 0
.
Визначте через скільки хвилин Микола зможе дістатися до місця проведення олімпіади, або виведіть -1, якщо він не зможе потрапити на олімпіаду.
Вхідні дані:
У першому рядку записані числа N, K(3 ≤ N ≤ 100, 1 ≤ K ≤ 1000).
У другому рядку записані номери зупинок А та В(1 ≤ A, B ≤ N).
Наступні K рядків містять описи кожного маршруту:
перше число M[i] у рядку означає кількість зупинок тролейбусного маршруту; далі розташовано Mi
* 2 - 1 чисел, які описують номери зупинок маршруту та час руху між ними (номер зупинки; час руху до наступної зупинки; номер наступної зупинки; час руху до наступної зупинки; номер наступної зупинки і т.д.).
Всі числа цілі.
Вихідні дані:
Час, який знадобиться Миколі, щоб доїхати до місця проведення олімпіади або -1, якщо Микола не зможе дістатися до місця призначення.
Пояснення.
Микола знаходиться на зупинці №1, йому потрібно дістатися до зупинки №8.
Існує три тролейбусних маршрути:
1-5-7-8 (та зворотній 8-7-5-1)
2-5-6-8 (та зворотній 8-6-5-2)
3-8-7-6-4 (та зворотній 4-6-7-8-3)
Микола виконує такі дії:
● у 0 момент часу (**t = 0**) сідає на зупинці №1 у тролейбус і через 2 хвилини виходить на зупинці №5 (**t = 2**);
● чекає хвилину і сідає на тролейбус, який прибуває із зупинки №2 (**t = 3**);
● проїжджає одну зупинку і виходить на зупинці №6 (**t = 4**);
● чекає дві хвилини, доки не прибуде тролейбус із зупинки №4 (**t = 6**);
● сідає і їде до зупинки №8 (**t = 10**).
8 3 1 8 4 1 2 5 6 7 5 8 4 2 3 5 1 6 8 8 5 3 9 8 3 7 1 6 6 4
10