5 Способ 2 — рекурсия с запоминанием

Способ 2 — рекурсия с запоминанием

Второй способ — короче и ближе к тому, как мы думаем о путях. Введём функцию f(curr, end) — длина кратчайшего пути из вершины curr в конечную вершину end. Тогда:

  • если мы уже в конце (curr == end) — идти никуда не нужно, длина 0;

  • если из curr не выходит ни одного ребра (тупик, не финиш) — до конца отсюда не добраться, возвращаем «бесконечность» (большое число);

  • иначе перебираем все рёбра curr → to весом w и берём минимум из w + f(to, end) — то есть «шаг по ребру плюс кратчайший путь дальше».

Чтобы не считать одну и ту же вершину много раз (иначе перебор разрастается), навешиваем запоминание результатов декоратором @lru_cache.

from collections import defaultdict
from functools import lru_cache

d = defaultdict(list)                       # список смежности: из вершины -> [ [куда, вес], ... ]
for s in open("23.txt"):
    frm, to, w = [float(x) for x in s.split()]
    d[frm].append([to, w])                  # добавляем ребро frm -> to весом w

@lru_cache(None)                            # запоминаем уже посчитанные вызовы
def f(curr, end):
    if curr == end:                         # дошли до конца — дальше идти не нужно
        return 0
    if curr not in d:                       # из curr нет рёбер — тупик
        return 10**8
    return min(w + f(to, end) for to, w in d[curr])   # лучший из ходов по рёбрам

print(int(f(1, 100)))                       # целая часть кратчайшего пути 1 -> 100

Разберём по частям:

  • d — список смежности: d[frm] хранит все рёбра, выходящие из вершины frm, в виде пар [куда, вес]. defaultdict(list) избавляет от проверок «а есть ли уже такой ключ».

  • f(curr, end) — рекурсивно спрашивает у соседей, за сколько они доводят до конца, и выбирает лучший вариант.

  • @lru_cache(None) — кэш: каждый f(curr, end) считается один раз, потом берётся из памяти. Без него на большом графе рекурсия была бы слишком медленной.

📌 Почему рекурсия не зациклится

Граф в задании 23 ациклический (это сказано в условии) — по стрелкам нельзя вернуться в уже пройденную вершину. Поэтому рекурсия всегда движется «вперёд, к финишу» и обязательно завершается. На графе с циклом такой способ зациклился бы — но здесь циклов нет.

📌 Тонкость с типами вершин

В коде номера вершин читаются как float (1.0, 100.0), а вызываем f(1, 100) целыми. Это работает, потому что в Python 1 == 1.0 и такие ключи совпадают в словаре. Хочешь чище — читай frm, to как int, а вес как float отдельно: a, b, w = s.split(); frm, to, w = int(a), int(b), float(w).

Оба способа на файле из примера печатают 7 — ответ один и тот же. Выбирай тот, что понятнее: Беллман–Форд короче по идее, рекурсия — нагляднее по смыслу «путь = шаг плюс путь дальше».

Способ 2 — рекурсия с запоминанием — Задание 23 ЕГЭ 2027 | Методички — Профиматика