Заправки
(Время: 1 сек. Память: 16 Мб Сложность: 49%)
В стране N городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-ый, потратив как можно меньшее количество денег.
Входные данные
Во входном файле INPUT.TXT записано сначала число N (1 ≤ N ≤ 100), затем идет N чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 100). Далее идет число M - количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами - номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число - суммарную стоимость маршрута или -1, если добраться невозможно.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
1 10 2 15
4
1 2
1 3
4 2
4 3
| 3 |
Пояснение к примеру
Оптимальное решение в примере: из 1-го города поехать в 3-й, а затем в 4-й. Горючее придется покупать в 1 и 3 городах.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
