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