Ленивые прогулки
Два друга настолько заботятся о расходе своих сил, что заранее подсчитали, сколько энергии у них уходит на переход из одной локации в соседнюю. Так, один из них знает, что потратит на это
A единиц энергии, а второй — B единиц энергии.Однако у них есть особый прием. Если оба оказываются в одной и той же локации, то один может понести другого, затратив
C единиц энергии вместо суммы A+B, которую они оба потратили бы, идя отдельно. При этом C не обязательно меньше, чем A+B, поэтому не всегда выгоднее так поступать.Первый друг начинает в локации 1, а второй — в локации 2. Им обоим нужно добраться до локации
n, израсходовав как можно меньше энергии. Вам нужно определить, какое минимальное общее количество энергии потребуется, чтобы они вдвоем смогли добраться до локации n.Входные данные
В первой строке вводятся 3 целых числа
A, B и C (1 ≤ A, B, C ≤ 50 000).Во второй строке содержатся 2 целых числа
n и e (1 ≤ n, e ≤ 100 000), где n — количество локаций, а e — количество соединений между ними.В следующих
e строках даются пары целых чисел и (1 ≤ ≤ n), которые указывают, что между этими двумя локациями существует связь.Выходные данные
Программа должна вывести минимальное общее количество энергии, необходимое, чтобы добраться до
n-й локации.Примеры
Входные данные | Выходные данные |
4 4 5
8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8 | 22 |
Пояснение
Friend 1: 1 → 4 ⇒ 4
Friend 2: 2 → 3 → 4 ⇒ 8
Together: 4 → 7 → 8 ⇒ 10
Итого: 4 + 8 + 10 = 22
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB