|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 06-3. Заправки
| Имя входного файла | input.txt |
| Имя выходного файла | output.txt |
| Максимальное время работы на одном тесте: | 5 секунд |
В стране N городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-ый, потратив как можно меньшее количество денег.
Формат входных данных
Во входном файле записано сначала число N (1<=N<=100), затем идет
N чисел, i-ое из которых задает стоимость бензина в
i-ом городе (все числа целые из диапазона от 0 до 100).
Затем идет число M - количество дорог в стране, далее идет описание
самих дорог. Каждая дорога задается двумя числами - номерами городов,
которые она соединяет. Все дороги двухсторонние (то есть по ним можно
ездить как в одну, так и в другую сторону); между двумя городами всегда
существует не более одной дороги; не существует дорог, ведущих
из города в себя.
Формат выходных данных
В выходной файл выведите одно число - суммарную стоимость маршрута
или -1, если добраться невозможно.
Пример
| input.txt | output.txt |
4 1 10 2 15 4 1 2 1 3 4 2 4 3 |
3 |
4 1 10 2 15 0 |
-1 |
В первом примере оптимальное решение - из 1-го города поехать в 3-й, а затем в 4-й. Горючее придется покупать в 1 и 3 городах.