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

Проверим маршруты из S в F, для которых суммарный расход энергии не превышает 8 единиц.

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

Из допустимых маршрутов наименьшее время имеет маршрут S–B–C–F.

Ответ: минимальное время — 8 единиц времени; маршрут S–B–C–F.