Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Железнодорожные тарифы

(Время: 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.TXTOUTPUT.TXT
12 0 2 11
23 2 2 3
1 2
2 3
3

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 A. Атрибутика
 B. Боксёры
 C. Вечерний пейзаж города К
 D. Генные модификации
 E. Деревянный забор
 F. E равно эм це квадрат?
 G. Ёлочные украшения
 H. Железнодорожные тарифы
 I. Загадали? Угадаем!
 J. Искусство алхимии
 K. Йодакойн
 L. Клумбы

Красноярский краевой Дворец пионеров, (c)2006 - 2022, ICQ: 151483, E-mail: admin@acmp.ru