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

Пример входного файла:

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

Пример выходного файла:
3

Решать не обязательно.. Просто объясните алгоритм..

Читаем про графы (Google поможет) и просветляемся.
На словах долго объяснять.

Это сообщение отредактировал(а) Игорь1024 - 19.12.2010, 07:04

Алгоритм Дейкстры

А если волновой алгоритм? Как его можно реализовать в данной задаче?

Я переписал bы его в поиск с учётом того что реbра не единичные. На самом деле это алгоритм A* bез эвристической функции. Тут недавно оbсуждалось как раbотатет А*. Может показаться интересным.


Это сообщение отредактировал(а) Леопольд - 19.12.2010, 19:04