6 Шпаргалка по заданию 23

Шпаргалка по заданию 23

Способ 1 — Беллман–Форд

edges = []
for s in open("23.txt"):
    a, b, w = s.split()
    edges.append((int(a), int(b), float(w)))

INF = 10**10
dist = [INF] * 1001
dist[1] = 0                             # старт
for _ in range(len(edges)):
    for a, b, w in edges:
        if dist[a] + w < dist[b]:
            dist[b] = dist[a] + w
print(int(dist[100]))                   # финиш — вершина 100

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

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])

@lru_cache(None)
def f(curr, end):
    if curr == end: return 0
    if curr not in d: return 10**8
    return min(w + f(to, end) for to, w in d[curr])

print(int(f(1, 100)))                   # старт 1, финиш 100

Что где менять

файл             имя приложенного файла в open(...)
старт            dist[1] = 0   (номер стартовой вершины)
финиш            print(int(dist[100]))  (номер конечной вершины)
целая часть      int(...)   отбрасывает дробную часть
вес — дробный    float(w)   (веса вещественные!)

⚠️ Типичные ошибки

1. Прочитал вес как целое (int) — веса вещественные, нужен float(w).

2. Забыл поставить dist[1] = 0 — тогда все расстояния останутся «бесконечными».

3. Сделал слишком мало проходов. Надёжно — повторить по всем рёбрам len(edges) раз.

4. Взял маленький массив dist. Вершины пронумерованы до 1000 — бери [INF]*1001.

5. Забыл про целую часть: в ответе — int(dist[100]), а не дробное число.

6. Перепутал направление ребра: a → b укорачивает путь до b, а не до a (граф ориентированный).

7. В рекурсии забыл @lru_cache — без запоминания на большом графе программа считает вечно.

8. В рекурсии перепутал базу: f(curr, end) возвращает 0 именно при curr == end, а тупик (curr not in d) — большое число.

💡 Последнее напутствие

Новое задание 23 решается коротким кодом — двумя способами на выбор. Беллман–Форд: поставил старту расстояние 0, много раз прошёлся по всем рёбрам, укорачивая пути, прочитал ответ у финиша. Рекурсия с запоминанием: длина пути = шаг по ребру плюс кратчайший путь дальше, а @lru_cache бережёт от повторов.

Не пугайся слов «граф» и «кратчайший путь»: любой из двух способов умещается в несколько строк и не ошибается. Бери тот, что понятнее именно тебе. Удачи на экзамене — Профиматика с тобой!

Шпаргалка по заданию 23 — Задание 23 ЕГЭ 2027 | Методички — Профиматика