Надіслати розв'язок

Бали: 40
Time limit: 2.0s
Memory limit: 250M

Author:
Problem type

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

Назар витрачає \(B\) одиниць енергії на перехід з одного пункту до сусіднього, а Юля витрачає \(E\) одиниць. Якщо Назар та Юля випадково опиняться в одному пункті, то Назар зможе понести Юлю на руках (якщо це буде енергетично вигідно), витративши \(P\) одиниць енергії для переміщення у сусідній пункт (\(P\) може бути меншим ніж \(B + E\)).

За заданим \(B\), \(E\), \(P\) і розташуванням пунктів, обчисліть мінімальну кількість енергії, яка буде потрібна Назару та Юлі щоб повернутися на базу.

Формат вхідних даних

Перший рядок містить додатні числа \(B\), \(E\), \(P\), \(N\), \(M\), які не перевищують 40000. \(N\) - кількість пунктів, пронумерованих від 1 до \(N\), (\(3 \le N\)). \(M\) - кількість шляхів між пунктами. Назар та Юля знаходяться на початку в пунктах 1 і 2 відповідно. База розташована в пункті \(N\).

Кожен з наступних \(M\) рядків описує шлях між пунктами. Шляхи двонаправлені. Завжди існує шлях від пункту 1 до пункту \(N\) і від пункту 2 до пункту \(N\).

Формат вихідних даних

Вивести одне число - мінімальну сумарну енергію, яку витратять Назар та Юля для повернення на базу.

Приклад вхідних даних

4 4 5 8 8 1 4 2 3 3 4 4 7 2 5 5 6 6 8 7 8

Приклад вихідних даних

22


Коментарі

Ще немає коментарів.