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