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