ЕГЭ Инфа PRO

🎯 ЕГЭ, задание 23: ищем минимальную длину пути из 1 в 100, но только если она в диапазоне [18 000; 22 000].

Найдите минимальную длину пути из вершины с номером 1 в вершину с номером 100 среди всех путей с длинами от 18000 до 22000 (включительно). Гарантируется, что хотя бы один такой маршрут существует. Запишите в ответе целую часть найденной длины.

Поэтому берём надёжную архитектуру: чёткие условия, настоящая бесконечность, никакой двойной арифметики.

✅ Готовый код — можно копировать на практику:

from collections import defaultdict
from functools import lru_cache

graf = defaultdict(list)
with open("23.txt") as f:
for line in f:
st, end, dl = line.split()
graf[int(end)].append((int(st), float(dl)))

@lru_cache(maxsize=None)
def dlina(x, sm):
if x == 1:
return 0.0 if 18000 <= sm <= 22000 else float('inf')
mn = float('inf')
for prev, w in graf[x]:
res = dlina(prev, sm + w)
if res != float('inf'):
mn = min(mn, res + w)
return mn

print(int(dlina(100, 0.0)))

#егэинформатика #задание23 #графы_егэ #алгоритмы_егэ #python_для_егэ #разбор_задания23 #айти #хрупкие_решения #подготовка_к_егэ

🧠 Разбор задачи: кратчайший путь ≤ 6 рёбер, отсекаем тупики/23 задания ЕГЭ
🎯 Задача

Найти целую часть длины кратчайшего пути из вершины 1 в вершину 100 в ориентированном ациклическом графе. Путь должен содержать не более 6 рёбер.

🔄 Хитрость решения: идём от конца к началу
Вместо того чтобы стартовать из 1 и натыкаться на тупики, запускаем поиск из 100 к 1 по обратному графу.
Почему это удобно: ветка, которая не ведёт к 1, просто не даст валидного пути — такие «лишние» вершины автоматически отсекаются.

💻 Код (обратный обход + кэш)

from collections import defaultdict
from functools import lru_cache

graf = defaultdict(list)
# Строим ОБРАТНЫЙ граф: end -> st
with open("23-1.txt") as f:
for line in f:
st, end, dl = line.split()
graf[int(end)].append((int(st), float(dl)))

@lru_cache(maxsize=None)
def dlina(x, steps):
# База: дошли до вершины 1 — путь найден
if x == 1:
return 0

# Лимит рёбер: нельзя больше 6 шагов
if steps >= 6:
return float('inf')

mn = float('inf')
for prev, w in graf[x]:
res = dlina(prev, steps + 1)
if res != float('inf'):
mn = min(mn, res + w)

return mn

result = dlina(100, 0)
print(int(result))

#егэ2024 #егэинформатика #задание23 #графы_егэ #работа_с_графами #алгоритмы_егэ #python_для_егэ #разбор_задания23 #подготовка_к_егэ_информатика #задачи_на_графы