АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

779. Заправки

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

В стране N городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-ый, потратив как можно меньшее количество денег.

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

Во входном файле записано сначала число N (1<=N<=100), затем идет N чисел, i-ое из которых задает стоимость бензина в i-ом городе (все это целые числа из диапазона от 0 до 100). Затем идет число M - количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами - номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.

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

Выведите одно число - суммарную стоимость маршрута или -1, если добраться невозможно.


Пример входных данных №1

4
1 10 2 15
4
1 2
1 3
4 2
4 3

Пример выходных данных №1

3

Комментарий: оптимальное решение - из 1-го города поехать в 3-й, а затем в 4-й. Горючее придется покупать в 1 и 3 городах.


Пример входных данных №2

4
1 10 2 15
0

Пример выходных данных №2

-1

Комментарий: добраться невозможно


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Учебные курсы / Задачи с olympiads.ru /
778. 252 - Дейкстра 779. 780. 254 - Заправки-2 781. 255 - Автобусы 685. 256 - Домой на электричках
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2019 / Графы /
746. 09 - Издевательство 779. 788. 11 - Цикл 1970. 12 - Автобусы 9. 13 - Сеть
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.