3. За какую наименьшую сумму можно добраться от острова A до острова G, используя данную паромную сеть? Стоимость проезда указана на схеме: AB — 600, AC — 300, BD — 100, CD — 400, BE — 400, DE — 300, CF — 100, DF — 200, EG — 100, FG — 700 рублей.

Сравним несколько маршрутов от A до G:

• A—C—F—G: 300 + 100 + 700 = 1100 рублей;
• A—C—D—E—G: 300 + 400 + 300 + 100 = 1100 рублей;
• A—B—E—G: 600 + 400 + 100 = 1100 рублей.

Чтобы обосновать, что меньшей суммы нет, учтём варианты выхода с острова A. Через C можно попасть к G по маршруту C—F—G за 800 рублей или C—D—E—G за 800 рублей; значит, с учётом переправы A—C сумма не меньше 300 + 800 = 1100 рублей. Через B самый дешёвый путь к G — B—E—G за 500 рублей; с переправой A—B получается 600 + 500 = 1100 рублей.

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