Новое задание 23 ЕГЭ-2027: графы с нуля и решение на Python

В новом задании 23 ЕГЭ по информатике 2027 нас ждут графы. Звучит как повод открыть толстый учебник, но начнём проще: представим карту дорог и попробуем добраться из одной точки в другую с минимальными затратами. Сначала разберём маленький пример, затем напишем решение на Python и проверим его на настоящем файле ФИПИ.

Что изменилось в задании 23

В опубликованном проекте ЕГЭ-2027 прежняя тема задания 23 — исполнитель с командами вроде «прибавь» и «умножь» — переехала в задание 13. Новое задание 23 посвящено графам: поиску оптимального пути и подсчёту путей. В этой статье разбираем поиск кратчайшего пути, который дан в демоверсии. Материал сверён с проектом ФИПИ на 6 ноября 2026 года.

Граф — это точки и связи между ними

Представьте карту с городами. Вершина — это город, ребро — дорога между городами. Возле дороги можно написать расстояние или стоимость проезда: это вес ребра. Тогда путь — несколько дорог, по которым мы последовательно добираемся до нужного города.

В задании граф ориентированный: у каждой дороги есть стрелка. Если она ведёт из 1 в 7, ехать можно именно из 1 в 7. Обратная дорога появится только тогда, когда она отдельно указана в файле. Навигатор здесь не разрешает разворачиваться по собственному желанию.

Ещё граф ациклический. Это означает, что, двигаясь по стрелкам, нельзя вернуться в ту же вершину. Слово длинное, а идея простая: круговых маршрутов нет. Номера вершин при этом могут идти в любом порядке — маленький номер вовсе не означает, что вершина стоит ближе к началу пути.

Что нужно найти в демоверсии ЕГЭ-2027

В файле demo_23.txt каждая строка описывает одну дорогу: откуда она ведёт, куда приходит и сколько стоит проход по ней. Нужно найти путь из вершины 1 в вершину 100 с наименьшей суммой весов, а в ответ записать целую часть этой суммы. Хотя бы один такой путь существует.

В демоверсии не более 200 рёбер, номера вершин — до 1000 и необязательно подряд. Веса положительные и могут быть дробными. Строки файла тоже не обязаны идти в порядке маршрута. Это пригодится нам при выборе решения: нельзя просто прочитать файл один раз и считать, что все нужные расстояния уже известны.

Разберём маленький пример вручную

Вот данные небольшого примера из самой демоверсии. Строка 1 7 5.5 означает дорогу из вершины 1 в вершину 7 с весом 5,5. В файле дробная часть отделяется точкой.

100 12 1.0
6 7 7.0
6 1 1.0
1 7 5.5
7 100 2.0
4 100 8.0
1 100 12.0
1 4 2.5

Из вершины 1 до вершины 100 здесь можно добраться тремя способами: напрямую за 12; через вершину 4 за 2,5 + 8 = 10,5; через вершину 7 за 5,5 + 2 = 7,5. Выбираем последний маршрут: 1 → 7 → 100. В ответ пойдёт 7, потому что нужна целая часть числа 7,5.

Вершина 6 нам не помогает: стрелка ведёт из неё в 1, а мы стартуем в 1 и не можем поехать против стрелки. Дорога из 100 в 12 тоже не нужна: финиш уже достигнут. Так большой на вид граф становится намного понятнее, если держать в голове старт и цель.

Идея решения: записываем лучший известный результат

Заведём список distance. В ячейке с номером вершины будем хранить лучшую найденную стоимость пути до неё. До старта идти не нужно, поэтому distance[1] = 0. Для остальных вершин сначала запишем бесконечность — отметку «путь пока не найден». Это не огромная стоимость билета, а просто удобное начальное значение.

Теперь просматриваем дороги. Допустим, до вершины 7 мы уже умеем добираться за 5,5, а дорога из 7 в 100 стоит 2. Значит, до 100 можно доехать за 7,5. Если раньше мы знали только путь за 12, заменяем 12 на 7,5. И так поступаем с каждой дорогой: нашли вариант дешевле — запомнили.

Проходим по всем дорогам несколько раз. Это нужно потому, что дорога из 7 в 100 могла встретиться в файле раньше, чем мы узнали хороший путь до 7. На следующем проходе новая информация дойдёт дальше. Когда за целый проход ничего не улучшилось, работа закончена. Такой подход называется алгоритмом Беллмана — Форда.

Готовое решение на Python

Скачайте официальный архив демоверсии ФИПИ и найдите в папке с файлами demo_23.txt. Сохраните программу ниже как solve.py в ту же папку. Дополнительные библиотеки устанавливать не нужно.

from decimal import Decimal

edges = []
with open("demo_23.txt") as file:
    for line in file:
        start, finish, weight = line.split()
        edges.append((int(start), int(finish), Decimal(weight)))

distance = [Decimal("Infinity")] * 1001
distance[1] = Decimal(0)

for _ in range(len(edges)):
    changed = False
    for start, finish, weight in edges:
        candidate = distance[start] + weight
        if candidate < distance[finish]:
            distance[finish] = candidate
            changed = True
    if not changed:
        break

print(int(distance[100]))

Откройте терминал в папке с обоими файлами и запустите программу. Если у Вас Python запускается командой python, используйте её вместо python3.

python3 solve.py

Для восьми строк маленького примера программа выводит 7. Для полного файла demo_23.txt из архива ФИПИ — 10971. Решение проверено на этом файле: результат совпадает с таблицей ответов демоверсии. Маленький пример в условии и полный файл — разные наборы данных, поэтому ответы у них разные.

Что здесь делает каждая часть программы

line.split() разделяет строку на три значения. Без аргументов этот метод справляется и с несколькими пробелами, и с табуляцией — в файле ФИПИ встречаются оба варианта. Номера вершин превращаем в целые числа, а каждую дорогу сохраняем в список edges.

Decimal(weight) читает вес как десятичное число. Так, например, сумма 0,1 и 0,9 получается ровно 1. Это удобно в задаче, где в конце нужно отбросить дробную часть. Модуль decimal уже входит в Python; важно передавать в него строку из файла, как в примере.

В списке distance 1001 ячейка: индексы идут от 0 до 1000. Нулевая ячейка нам не нужна, зато номер вершины можно использовать прямо как индекс. Выражение distance[start] + weight считает стоимость нового варианта пути, а условие candidate < distance[finish] проверяет, стал ли он дешевле.

Переменная changed запоминает, было ли хоть одно улучшение за проход. Если нет, команда break завершает цикл. Последняя строка print(int(distance[100])) выводит целую часть найденной положительной длины. Здесь нам нужен int, а не round: 7,5 должно превратиться в 7, а не в 8.

Почему достаточно нескольких проходов

За первый проход программа гарантированно найдёт лучшие пути из одного ребра, за второй — из двух, и так далее. Иногда она успеет продвинуться дальше за один проход: это зависит от порядка строк. Но рассчитывать на удачный порядок нам не нужно.

В пути без циклов не может быть больше рёбер, чем всего записано в файле. Поэтому len(edges) проходов достаточно. В демоверсии максимум 200 рёбер: даже полный перебор всех дорог на каждом из 200 проходов даст лишь 40 000 проверок. А остановка по changed часто завершит работу раньше.

Ошибки, из-за которых теряется правильный ответ

Выбрать самую дешёвую дорогу на каждом шаге. В маленьком примере из вершины 1 дешевле всего сначала поехать в 4: всего 2,5. Но весь маршрут через 4 стоит 10,5, а через 7 — 7,5. Сравнивать нужно стоимость полного пути.

Обработать вершины по возрастанию номеров. Номера — просто метки. В файле допустима дорога из 900 в 7, поэтому сортировка по номеру не создаёт правильный порядок вычислений. Наше решение повторяет проходы и не зависит от такой нумерации.

Добавить обратные дороги или обрезать дроби заранее. Храним только направления из файла и считаем с дробными весами до самого конца. Например, два ребра по 0,6 дают путь длиной 1,2. Если заранее превратить каждый вес в целое число, вместо правильного ответа 1 получится 0.

Получить FileNotFoundError. Это означает, что Python не нашёл файл по указанному пути. Проверьте имя demo_23.txt и папку, из которой запускаете программу. В IDE рабочая папка может отличаться от папки со скриптом; для проверки можно указать полный путь к файлу в open.

Три короткие проверки для себя

1. В маленьком примере замените вес прямой дороги из 1 в 100 с 12,0 на 6,9. Какой маршрут теперь победит? Ответ: прямой путь, программа выведет 6.

2. Верните исходные данные и удалите дорогу из 1 в 7. Что останется? Ответ: маршрут 1 → 4 → 100 длиной 10,5; программа выведет 10.

3. Переставьте строки исходного маленького файла в обратном порядке. Должен ли измениться ответ? Нет: снова получится 7. Если после перестановки результат другой, программе, вероятно, не хватает повторных проходов.

Теперь попробуйте рассказать решение своими словами: что хранится в distance, когда значение меняется и почему нужен ещё один проход по файлу. Если эти три вещи понятны, граф уже перестаёт быть загадочным клубком стрелок.