№ 9. Робот едет из S в F. Рёбра (время; энергия): S–A (3;2), S–B (2;4), A–C (2;3), B–C (1;2), C–F (2;3), A–F (6;2), B–F (5;3), A–B (1;2). Заряд 7 ед. Дороги двусторонние, подзарядки нет; маршрут допустим, если суммарный расход энергии не больше заряда. Найдите минимальное время среди допустимых по энергии маршрутов.

Проверим маршруты из S в F:

• S–A–C–F: время \(3+2+2=7\), энергия \(2+3+3=8\) — недопустим.
• S–B–C–F: время \(2+1+2=5\), энергия \(4+2+3=9\) — недопустим.
• S–A–F: время \(3+6=9\), энергия \(2+2=4\) — допустим.
• S–B–F: время \(2+5=7\), энергия \(4+3=7\) — допустим.
• S–A–B–F: время \(3+1+5=9\), энергия \(2+2+3=7\) — допустим.

Среди допустимых маршрутов минимальное время равно 7.

Ответ: 7