eolymp
Соревнования

ADA University - February 3 - Dijkstra

Путешествие

Армия Речи Посполитой движется из города Костромы в деревню Домнино. Два гетмана Стефан и Константин ведут армию.

Стефан приобрел карту Костромской области, и каждую ночь он ведет армию от одной деревни к другой по некоторой дороге. Константин достал карту секретных троп между деревнями, и каждый день ведет армию по одной из этих троп. Каждый гетман спрашивает у их проводника Ивана Сусанина какой путь выбрать перед каждым маршем.

Длина каждой дороги указана на карте у Стефана. Поэтому Стефан знает длину минимального расстояния между каждой деревней и деревней Домнино согласно своей карты. Аналогично и Константин тоже знает кратчайшие расстояние между каждой деревней и Домнино, которые проходят по тропам согласно его карте.

Иван Сусанин, будучи секретным агентом, не хочет разоблачить себя. Поэтому каждый раз он выбирает дорогу (для Стефана) и тропу (для Константина) таким образом, чтобы кратчайшее расстояние до деревни Домнино согласно карте гетмана, который задает вопрос, строго уменьшалось.

prb2267

Помогите Ивану найти самый длинный возможный путь до деревни Домнино.

Входные данные

Первая строка содержит три целых числа n, s и t - количество деревень в Костромской области, а также номера начальной деревни и деревни Домнино (2n1000, 1s, tn). Деревни пронумерованы числами от 1 до n. Начальная деревня и деревня Домнино не совпадают.

Далее следуют два блока. Первый задает карту Стефана, а второй карту Константина.

Первая строка каждого блока содержит целое число m - количество дорог/троп между деревнями (n - 1m105). Каждая из следующих m строк содержит три целых числа a, b и l - они описывают дорогу/тропу между деревнями a и b длины l (1a, bn; 1l106).

Армия Речи Посполитой может двигаться в любом направлении по дороге или тропе. Известно, что каждый гетман может пройти из любой деревни в любую согласно своей карты. Армия стартует вечером из заданной начальной деревни и двигается по одной дороге каждую ночь и по одной тропе каждый день.

Выходные данные

Вывести длину самого длинного пути, по которому может провести Иван Сусанин армию Речи Посполитой пока она не достигнет деревни Домнино (по дорогам и тропам). Если Иван Сусанин сможет бесконечно водить армию, не достигнув деревни Домнино, то вывести число "-1".

Лимит времени 1 секунда
Лимит использования памяти 256 MiB
Входные данные #1
5 1 5
5
1 2 2
1 4 2
2 3 1
3 4 1
5 3 1
4
1 2 2
2 4 2
2 3 1
2 5 2
Выходные данные #1
-1
Входные данные #2
3 1 3
4
1 2 10
2 3 10
1 3 20
2 3 30
4
2 1 10
1 3 10
1 1 10
2 3 10
Выходные данные #2
20
Автор Mikhail Dvorkin, Dmitry Gozman
Источник 2010 NEERC Northern Subregional St Petersburg, October 30