сложная задача с олимпиады по программированию

Перевозчику необходимо доставить груз из одного города (А) в другое (В). Известно, что при доставке груза перевозчик несет затраты связанные по транспортировке товара и оплате «пошлины» [взимается определенная сумма при проезде через город транзитом], в городах ((А)(В)) с которого и до которого перевозится товар «пошлину» с перевозчика не оплачивается.

Составить программу которая находит оптимальный маршрут доставки товара между двумя городами. Суммы «пошлины», которые взимает каждое из городов известны. Известна также информация о том, между какими городами есть прямое соединение и стоимость перевозки по этому соединенные.

Входные данные

Первая строка входного файла содержит два целых числа N (количество городов) (1≤N≤100) и M (количество дорог) (1≤M≤100) .

Вторая строка содержит N действительных чисел, которые задают сумму «пошлины» для каждого из городов. В каждом следующем из M строк файла содержится тройка чисел (для примера тройка 2 5 130 - задает сообщение между вторым городом и пятым и затраты на транспортировку). В последней строке файла заданы два целых числа ( А и В) .

Исходные данные

Первая строка выходного файла содержит последовательность целых чисел, которые задают маршрут, вторая строка – общую сумму затрат на перевозки

0

Bison5, точно помню, что расчет оптимального пути есть в книге Роберта Лафоре по алгоритмам, в последних главах связанных с графами, а так же у Сэджвика (все по тем же алгоритмам).

0

Решается "сложная" задачка элементарно с помощью алгоритма Дейкстры.

0