e-olymp
Yarışlar

III этап Всеукраинской олимпиады по информатике 2011-2012 г. Житомир 1 тур

Метро

prb2795 Метрополитен состоит из L линий, на которых розмещены N станций с номерами от 1 до N. Каждая станция принадлежит одной или больше линиям. Если станция принадлежит нескольким линиям, то она является узловой и на ней можно пересесть на любую другую линию, проходящую через неё. Каждая линия состоит из двух или более станций и имеет хотя бы одну узловую. Между любыми двумя станциями метрополитена существует сообщение, причём стоимость проезда равна минимальному из двух значений:

  1. A копеек насчитывается за каждую станцию на пути следования, включая посадку и высадку;
  2. B копеек насчитывается за каждую из использованных линий.

Какая минимальная сумма в копейках достаточна, чтобы добраться от станции номер i до станции j?

Входные данные

В первой строке записаны четыре натуральных числа N, L, A и B. В L последующих строках записаны последовательные номера станций каждой линии метро. Последняя строка содержит номера i начальной и j конечной станции. Все числовые значения натуральны, L10, другие значения не превышают 100.

Выходные данные

Минимальная сумма в копейках для поездки.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
7 3 10 20
2 1 3
6 1 4 5
5 7
2 7
Çıxış verilənləri #1
50

Şərh: Оплата за посещённые станции будет 5x10=50 коп., а за использованные линии 3x20=60 коп.

Mənbə Stage III All-Ukrainian School Olympiad 2011-2012, Round 1, Zhytomyr