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

а) Каждый переход между соседними островами занимает 3 часа. Чтобы найти кратчайшее время, достаточно определить маршрут с наименьшим числом переправ.

Маршрут A—B—E—G содержит 3 переправы, поэтому время в пути равно \(3\cdot3=9\) часов. Меньше трёх переправ не получится: от A до G нужно пройти как минимум через B и E либо через C, F и G.

Ответ: 9 часов.

б) Сравним стоимости возможных маршрутов. По маршруту A—B—E—G стоимость составляет \(100+200+1100=1400\) рублей. По маршруту A—C—F—G стоимость составляет \(900+100+300=1300\) рублей.

Проверим более дешёвые варианты через D: A—B—D—F—G стоит \(100+600+400+300=1400\) рублей; A—C—D—E—G стоит \(900+200+300+1100=2500\) рублей. Следовательно, самый дешёвый маршрут — A—C—F—G.

Ответ: 1300 рублей.