Анонс #116. Вагонетка

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

Входные данные: OilCosts = [oilCost_1, oilCost_2, ... oilCost_N] - массив, где oilCost(i) - стоимость канистры горючего в i-м поселке. 

TrainRoads = [ (Ai, Bj) ] - массив, где (Ai, Bj) - железная дорога, ктр соединяет поселок Ai c поселком Bj.

Дороги двухсторонние, и разумеется, между любыми двумя поселками не более 1 одной дороги.

Вывод: вывести оптимальный маршрут, т.е. номера поселков на этом маршруте.

Пример:

OilCosts = [5, 10, 1]

TrainRoads = [ (1, 3), (1, 2), (3, 2) ]

Answer: 1 -> 3