🧠 Разбор задачи: кратчайший путь ≤ 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 #подготовка_к_егэ_информатика #задачи_на_графы