Определите самый дешевый маршрут из МУХА в ЖИРАФ. Проезд по магистралям возможен в обоих направлениях, однако в стране действует закон: выезжая из города А, путешественник обязан на весь ближайший отрезок до города Б закупить топливо по ценам, установленным в городе А. Определите самый дешевый маршрут из МУХА в ЖИРАФ.
В одной сказочной стране всего 5 городов, которые соединены между собой непересекающимися магистралями. Расход топлива для каждого отрезка и цены на топливо приведены в таблице:
Город А | Город Б | Расход топлива (л) | Цена 1 л топлива в городе А (у.е.) |
МУХА | СЛОН | 6 | 10 |
МУХА | КРОКОДИЛ | 7 | 10 |
МУХА | БЕГЕМОТ | 8 | 10 |
СЛОН | КРОКОДИЛ | 10 | 2 |
СЛОН | ЖИРАФ | 16 | 2 |
КРОКОДИЛ | СЛОН | 15 | 2 |
КРОКОДИЛ | БЕГЕМОТ | 10 | 2 |
БЕГЕМОТ | ЖИРАФ | 1 | 10 |
1) МУХА – СЛОН – ЖИРАФ
2) МУХА – БЕГЕМОТ – ЖИРАФ
3) МУХА – КРОКОДИЛ – БЕГЕМОТ – ЖИРАФ
4) МУХА – КРОКОДИЛ – СЛОН – ЖИРАФ
Ответ: