Е1.8 Определите самый дешевый маршрут из МУХА в ЖИРАФ

Определите самый дешевый маршрут из МУХА в ЖИРАФ. Проезд по магистралям возможен в обоих направлениях, однако в стране действует закон: выезжая из города А, путешественник обязан на весь ближайший отрезок до города Б закупить топливо по ценам, установленным в городе А. Определите самый дешевый маршрут из МУХА в ЖИРАФ.

В одной сказочной стране всего 5 городов, которые соединены между собой непересекающимися магистралями. Расход топлива для каждого отрезка и цены на топливо приведены в таблице:

Город А Город Б        Расход топлива (л)    Цена 1 л топлива в городе А (у.е.)
МУХА СЛОН 6 10
МУХА КРОКОДИЛ 7 10
МУХА БЕГЕМОТ 8 10
СЛОН КРОКОДИЛ 10 2
СЛОН ЖИРАФ 16 2
КРОКОДИЛ СЛОН 15 2
КРОКОДИЛ БЕГЕМОТ 10 2
БЕГЕМОТ ЖИРАФ 1 10

1) МУХА – СЛОН – ЖИРАФ

2) МУХА – БЕГЕМОТ – ЖИРАФ

3) МУХА – КРОКОДИЛ – БЕГЕМОТ – ЖИРАФ

4) МУХА – КРОКОДИЛ – СЛОН – ЖИРАФ

Ответ:

Добавить комментарий