e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dijkstra algorithm

Заправки

У країні n міст, деякі з яких з'єднані між собою дорогами. Для того, щоб проїхати по одній дорозі потрібно один бак бензину. У кожному місті бак бензину має різну віртість. Вам потрібно дістатись з першого міста у n-те, витративши якомога меншу кількість грошей.

Вхідні дані

Спочатку йде кількість міст n (1n100), потім йде n чисел, i-те з яких задає вартість бензину у i-ому місті (всі числа цілі з діапазону від 0 до 100). Потім йде кількість доріг m в країні, далі йде опис самих доріг. Кожна дорога задається двома числами - номерами міст, які вона з'єднує. Всі дороги двосторонні (тобто по ним можна їздити як в одну, так і в іншу сторону); між двома містами завжди існує не більше однієї дороги; не існує доріг, які ведуть з міста в себе.

Вихідні дані

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

prb1388.gif

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4
1 10 2 15
4
1 2 1 3 4 2 4 3
Вихідні дані #1
3
Вхідні дані #2
4
1 10 2 15
0
Вихідні дані #2
-1

Пояснення: У першому прикладі оптимальний розвязок - з 1-го міста поїхати в 3-тє, а потім у 4-те. Паливо прийдеться купувати у 1-му і 3-му містах