Архипелаг из семи островов соединён паромными переправами. Стоимость проезда на каждом пароме (в рублях) указана на схеме.
Рёбра схемы: A–B — 100, A–C — 900, B–E — 200, B–D — 600, E–D — 300, E–G — 1100, D–C — 200, D–F — 400, C–F — 100, F–G — 300.
Переправа между соседними островами занимает 3 часа.
а) За какое наименьшее время можно добраться от острова A до острова G, используя данную паромную сеть? Ответ выразите в часах.
б) За какую наименьшую сумму можно добраться от острова A до острова G, используя данную паромную сеть? Проезд не обязательно должен занимать наименьшее время. Ответ выразите в рублях.
а) С острова A можно попасть только на B и C. На остров G можно попасть только с E и F. Общих соседей у A и G нет, поэтому за
За
Время:
б) Найдём наименьшую стоимость проезда от A до каждого острова:
- B:
(прямо). - E:
. - D:
(через B и E; напрямую от B стоило бы , это дороже). - C: через D
(прямо стоило бы , это дороже). - F: через C
(через D стоило бы , это дороже). - G: через F
(через E стоило бы , это дороже).
Самый дешёвый путь: A → B → E → D → C → F → G.
В пункте а) считаем наименьшее число переправ, в пункте б) ищем самый дешёвый путь: наименьшую стоимость для каждого острова подсчитываем по порядку, начиная с A. Самый дешёвый путь может быть длиннее по числу переправ.
а)
б)
