Пост канала
- фото
💻 Разбираем задание № 32027 с Kompege.ru — добавляем ограничения в поиск кратчайшего пути! Сегодня берём непростое, но очень показательное задание: нужно найти кратчайший путь в графе, но с двумя дополнительными условиями: ✅ путь обязательно должен проходить через вершину 400; ❌ и при этом не должен проходить через вершину 68. Такие условия — отличный тренажёр для понимания, как адаптировать базовые алгоритмы под реальные задачи ЕГЭ‑2027 (задание 23). Давайте разберём, как это реализовать на практике. 🗺️ Стратегия решения Самый надёжный и понятный способ — разбить задачу на два этапа: Сначала ищем кратчайший путь от старта до обязательной вершины 400, исключив из рассмотрения вершину 68. Затем — от вершины 400 до финиша, снова не заходя в 68. Итоговая длина пути — это сумма двух найденных расстояний. Такой подход работает, потому что он опирается на свойство оптимальности подструктур: если весь путь оптимален, то и его части тоже должны быть оптимальными. 🔧 Как технически исключить вершину 68 Для рекурсии с lru_cache: если текущая вершина — 68, возвращаем бесконечность (float('inf')), чтобы этот путь никогда не был выбран как минимальный. Обратите внимание: мы не усложняем саму функцию дополнительными параметрами — достаточно просто «заблокировать» вершину 68 внутри неё. А обязательную вершину 400 обрабатываем на уровне вызова: путь становится композицией двух независимых задач.
Открыть в MAX- Просмотры
- 22
- ER
- 4,5%
- Реакции
- 1