Задание 4. Архипелаг из семи островов соединён паромными переправами. Стоимость проезда на каждом пароме (в рублях) указана на схеме. Переправа между соседними островами занимает 3 часа. а) За какое наименьшее время можно добраться от острова A до острова G, используя данную паромную сеть? Ответ выразите в часах. б) За какую наименьшую сумму можно добраться от острова A до острова G, используя данную паромную сеть? Проезд не обязательно должен занимать наименьшее время. Ответ выразите в рублях.

Наименьшее время определяется количеством переправ. Кратчайший путь по числу переправ: A → B → E → G — 3 переправы.

Время: 3 · 3 = 9 часов.

Для наименьшей стоимости сравним подходящие маршруты. По пути A → B → E → G стоимость равна 100 + 200 + 1100 = 1400 рублей. По пути A → C → F → G стоимость равна 900 + 100 + 300 = 1300 рублей. Ещё дешевле маршрут A → B → D → F → G: 100 + 600 + 400 + 300 = 1400 рублей, а A → B → E → D → F → G стоит 100 + 200 + 300 + 400 + 300 = 1300 рублей. Минимальная стоимость — 1300 рублей.

Ответ: а) 9 часов; б) 1300 рублей.