|
Железнодорожные тарифы
(Время: 5 сек. Память: 64 Мб Сложность: 57%)
На территории Империи расположены n городов, между каждой парой городов есть прямое беспересадочное сообщение в обе стороны либо на поезде дальнего следования, либо на электричке. Согласно текущей тарификации, беспересадочная поездка на поезде стоит A монет, беспересадочная поездка на электричке стоит B монет.
Требуется найти минимальную сумму, за которую пассажир может добраться из города в провинции у моря, который имеет номер n, до столицы, которая имеет номер 1.
Входные данные
Первая строка входного файла INPUT.TXT содержит четыре целых числа n, k, A и B – общее количество городов в Империи, количество пар городов, между которыми есть прямое сообщение на поезде, цену поездки на поезде и цену поездки на электричке соответственно (2 ≤ n ≤ 105, 0 ≤ k ≤ min(n×(n–1)/2, 5×105), 1 ≤ A,B ≤ 109). Каждая из последующих k строк содержит по два целых числа p и q (1 ≤ p, q ≤ n, p ≠ q) – номера очередных городов, между которыми ходит безостановочный поезд дальнего следования.
Остальные n×(n–1)/2–k пар городов, соответственно, соединены беспересадочными электричками.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – минимальную сумму, которая требуется для проезда из города n в город 1.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 2 0 2 1 | 1 |
2 | 3 2 2 3 1 2 2 3 | 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |