Реши задачу в файле
Сверь числа и знаки с фото.
Робот едет из S в F. Рёбра (время; энергия): S–A (4;1), S–B (2;3), A–C (1;4), B–C (2;1), C–F (3;2), A–F (8;2), B–F (6;4), A–B (1;2). Заряд 6 ед. Дороги двусторонние, подзарядки нет; маршрут допустим, если суммарный расход энергии не больше заряда. Найдите минимальное время среди допустимых по энергии маршрутов.
Ответ: 7.
Подходящий маршрут — \(S\to B\to C\to F\). Для него:
\[ t=2+2+3=7,\qquad E=3+1+2=6. \]
Условие \(E\le 6\) выполнено, значит, маршрут допустим и даёт время \(7\).
Почему меньше нельзя. Времена и расходы энергии положительны, поэтому повторять вершины бессмысленно.
- Если первый шаг из \(S\) идёт в \(A\), то только на него уходит \(4\). Самый быстрый путь через \(A\) — \(S\to A\to C\to F\), но он занимает \(8\) единиц времени, то есть всё равно больше \(7\). К тому же его энергия \(1+4+2=7>6\), так что он ещё и недопустим.
- Если первый шаг идёт в \(B\), то до \(B\) время равно \(2\). Минимальное время от \(B\) до \(F\) — \(5\) единиц: \(B\to C\to F\). Поэтому быстрее \(7\) не получится. Другой маршрут \(S\to B\to A\to C\to F\) тоже занимает \(7\), но тратит \(3+2+4+2=11>6\).
Проверка: маршрут \(S\to B\to C\to F\) расходует ровно \(6\) единиц энергии, а по условию разрешено «не больше заряда», то есть \(6\le6\). Минимальное время — 7.
