Модуль: Алгоритм Дейкстры


Задача

4 /14


Заправки

Задача

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

Примеры
Входные данные Выходные данные
1
5
3 6 1 7 6 
8
1 2
5 4
5 1
3 4
5 2
2 4
2 3
3 1
3



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6497
Java1
Python45
Комментарий учителя