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

Dijkstra algorithm

Таксі

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

Таксі виїжджає з пункту А, де проживає Іван, прямує до пункту В, забираючи Сергія і далі їде до місця проведення олімпіади (пункт С).

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

Відомо, що таксі завжди вибирає найкоротший з існуючих маршрутів.

Вхідні дані

В першому рядку записано п'ять чисел - чотири цілих та одне дійсне:

n – кількість населених пунктів,

A – населений пункт, де проживає Іван,

B – населений пункт, де проживає Сергій,

С – населений пункт, де проходить олімпіада,

d – вартість проїзду 1 кілометру на таксі. 

Наступний рядок містить кількість доріг m. Кожен з наступних m рядків описує дорогу – два цілих числа (номери населених пунктів, які сполучає дорога) та дійсне число - довжина відповідної дороги в кілометрах.

Усі цілі числа натуральні та не більші 100.

Вихідні дані

Виведіть дійсне число - суму, на яку довелося заплатити більше, заїжджаючи за Сергієм або –1, якщо з пункту А не існує маршруту до населеного пункту, де проживає Сергій, або з пункту А не існує маршруту до місця проведення олімпіади.

Z1_2.jpg

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5 1 2 3 4.25
5
1 4 2.5
4 2 3
4 5 3
3 5 2
3 4 8
Вихідні дані #1
25.5
Джерело 2020 XXXIV обласна олімпіада з інформатики, Житомир