e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dijkstra algorithm

Мандри

Армія Речі Посполитої рухається з міста Кострома у село Домніно. Два гетьмана Стефан і Костянтин ведуть армію.

Стефан придбав карту Костромської області, і щоночі він веде армію від одного села до іншого по деякій дорозі. Костянтин дістав карту секретних стежок між селами, і кожен день веде армію по одній з цих стежок. Кожен гетьман запитує у їх провідника Івана Сусаніна який шлях обрати перед кожним маршем.

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

Іван Сусанін, будучи секретним агентом, не хоче викрити себе. Тому кожен раз він вибирає дорогу (для Стефана) і стежку (для Костянтина) таким чином, щоб найкоротша відстань до села Домніно відповідно до кари гетьмана, який ставить запитання, строго зменшувалася.

prb2267

Допоможіть Івану знайти найдовший можливий шлях до села Домніно.

Вхідні дані

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

Далі йдуть два блоки. Перший задає карту Стефана, а другий карту Костянтина.

Перший рядок кожного блоку містить ціле число m - кількість доріг/стежок між селами (n - 1m100000). Кожен з наступних 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