eolymp
bolt
Try our new interface for solving problems
Məsələlər

Заправки

Заправки

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

Giriş verilənləri

Сначала идет количество городов n~(1 \le n \le 100), затем идет n чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 100). Затем идет количество дорог m в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами — номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
4
1 10 2 15
4
1 2 1 3 4 2 4 3
Çıxış verilənləri #1
3
Giriş verilənləri #2
4
1 10 2 15
0
Çıxış verilənləri #2
-1