Повышенный (1 балл) Время: 4-7 мин Python heapq / BFS Списки смежности Файловый ввод (L, M, W) Все задачи №23 в каталоге

Задание №23. Графы и алгоритмы

Тема: Кратчайшие пути в ориентированных взвешенных графах, Дейкстра и обход графов

Чтение описания ориентированного взвешенного графа из текстового файла (например, 23-1.txt), поиск кратчайшего пути с ограничением на максимальное число рёбер и вычисление суммы номеров промежуточных вершин или длины пути.

1. Структура входного файла (23-1.txt):

Каждая строка файла содержит L M W, где $L$ и $M$ — вершины, $W$ — вес ребра из $L$ в $M$.

graph = {}
with open('23-1.txt') as f:
    for line in f:
        parts = line.split()
        if not parts: continue
        u, v, w = int(parts[0]), int(parts[1]), float(parts[2])
        graph.setdefault(u, []).append((v, w))

2. Поиск кратчайшего пути с ограничением на количество рёбер:

Используем алгоритм Дейкстры с сохранением состояния (вершина, число рёбер):

Разновидности и прототипы задания на экзамене

Тип 1: Кратчайший путь с ограничением на количество рёбер

Поиск пути из вершины A в B, содержащего не более K рёбер, минимизируя суммарный вес.

Тип 2: Сумма номеров промежуточных вершин

Восстановление пути и подсчёт суммы вершин вдоль оптимального маршрута.

Тип 3: Целая часть длины кратчайшего пути

Вычисление точного веса с дробными весами рёбер и округление вниз (int).

Боевой шаблон решения на Python

Запустить код в онлайн-песочнице

Боевой шаблон решения на Python

# === Боевой шаблон Задания №23 ЕГЭ 2026 на Python ===
import heapq

# 1. Чтение графа из файла
graph = {}
with open('23-1.txt') as f:
    for line in f:
        parts = line.split()
        if not parts:
            continue
        u, v, w = int(parts[0]), int(parts[1]), float(parts[2])
        graph.setdefault(u, []).append((v, w))

# 2. Дейкстра с ограничением не более 6 рёбер (из вершины 1 в 100)
# Состояние очереди: (суммарный_вес, текущая_вершина, число_рёбер, путь)
pq = [(0.0, 1, 0, [1])]
best = {}

ans_dist = None
ans_path = None

while pq:
    d, u, edges, path = heapq.heappop(pq)
    
    if u == 100:
        ans_dist = d
        ans_path = path
        break
        
    if edges >= 6:
        continue
        
    state = (u, edges)
    if state in best and best[state] <= d:
        continue
    best[state] = d
    
    for v, w in graph.get(u, []):
        heapq.heappush(pq, (d + w, v, edges + 1, path + [v]))

print("Длина кратчайшего пути:", ans_dist)
print("Целая часть длины:", int(ans_dist))
print("Маршрут:", ans_path)
# Сумма промежуточных вершин:
if ans_path:
    intermediates = ans_path[1:-1]
    print("Сумма промежуточных вершин:", sum(intermediates))

Задача из базы, которую решает этот код Открыть в песочнице

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

✕ Не так

Ошибка: Забыть ограничение на число рёбер (edges <= K)

Обычный Дейкстра найдёт глобально кратчайший путь, но в нём может оказаться больше допустимого числа рёбер!

✓ Так

Правильно: Хранить в состоянии пары (вершина, число рёбер) и отсекать ветви при edges >= max_edges.

ГРОБ

ГРОБ №23: Граф с большим числом вершин и циклы

Если граф содержит циклы с нулевым или малым весом, поиск в глубину без мемоизации зациклится.

Как обойти

Алгоритм Дейкстры с очередью приоритетов heapq гарантирует извлечение путей в порядке возрастания веса и предотвращает бесконечные циклы.

Лайфхаки на экзамене

При чтении чисел используйте parts = line.split(), так как разделителем могут быть пробелы и табуляции.
Вес $W$ может быть вещественным (float), поэтому преобразуйте веса через float(parts[2]).

Банк реальных задач №23 Открыть в тренажере СмартКИМ