Задание 23 ЕГЭ по информатике 2027 — граф из файла: кратчайший путь и число путей
Разбор задания 23 ЕГЭ по информатике 2027: ориентированный ациклический граф в текстовом файле, целая часть длины кратчайшего пути из 1 в 100 (ответ 10971), количество путей, тупики и недостижимые вершины. Рекурсия с кешем на Python.
Задание 23 в 2027 году — единственная по-настоящему новая тема экзамена: граф в текстовом файле. В каждой строке два номера вершин и вес ребра, граф ориентированный и ациклический, а вопрос — целая часть длины кратчайшего пути из вершины 1 в вершину 100 (в демо ответ 10971) или количество различных путей. Решается рекурсией с кешем в пятнадцать строк. Ниже — условие демо, разбор типового примера руками, код, ловушки файла и вариации вопроса.
До 2027 года под номером 23 был исполнитель и количество программ — теперь это задание 13, и его старый разбор лежит в статье 2026 года. Рекурсия с кешем из того разбора пригодится и здесь.
Условие демоверсии 2027
В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке записаны два натуральных числа (L, M) и одно положительное вещественное число (W): L и M — номера вершин, W — вес ребра, ведущего из L в M. Количество строк равно количеству рёбер; две вершины не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100. Существование хотя бы одного пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.
Вершины могут быть пронумерованы не подряд; L ≤ 1000, M ≤ 1000, W ≤ 10 000; строк не больше 200; числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Типовой пример организации данных во входном файле:
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
Для приведённого примера верным ответом будет 7. Ответ ФИПИ для файла демо: 10971.
Разбор типового примера руками
Выпишем, куда ведут рёбра из каждой вершины:
| Вершина | Исходящие рёбра |
|---|---|
| 1 | → 7 (5.5), → 100 (12.0), → 4 (2.5) |
| 4 | → 100 (8.0) |
| 6 | → 7 (7.0), → 1 (1.0) |
| 7 | → 100 (2.0) |
| 100 | → 12 (1.0) |
| 12 | — |
Пути из 1 в 100 и их длины:
| Путь | Длина |
|---|---|
| 1 → 7 → 100 | 5.5 + 2.0 = 7.5 |
| 1 → 4 → 100 | 2.5 + 8.0 = 10.5 |
| 1 → 100 | 12.0 |
Кратчайший — 7.5, целая часть 7. Путей три, самый длинный — 12. Эти три числа — проверка шаблона перед запуском на файле.
Пример показывает все ловушки сразу. Вершина 12 — тупик: из неё нет рёбер. Вершина 6 недостижима из 1: в неё ничего не ведёт, хотя из неё ведут рёбра, в том числе обратно в 1. Из конечной вершины 100 есть ребро наружу, в 12, — путь должен закончиться на 100, а не продолжаться.
Решение на Python
from functools import lru_cache
START = 1
FINISH = 100
INF = float("inf")
g = {}
with open("demo_23.txt") as f:
for line in f:
parts = line.split()
if len(parts) < 3:
continue
a = int(parts[0])
b = int(parts[1])
if a not in g:
g[a] = []
g[a].append((b, float(parts[2])))
@lru_cache(None)
def short(v):
if v == FINISH:
return 0.0
best = INF
for m, w in g.get(v, []):
step = short(m) + w
if step < best:
best = step
return best
@lru_cache(None)
def paths(v):
if v == FINISH:
return 1
total = 0
for m, w in g.get(v, []):
total += paths(m)
return total
print(int(short(START))) # 10971
print(paths(START)) # 2033652335
По строкам. line.split() без аргумента режет по любому числу пробелов и табуляций — ровно то, что обещает условие. Вес читается как float: на записи 72.6 функция int упала бы. Граф лежит в словаре, потому что вершины пронумерованы не подряд и доходят до тысячи.
Функция short(v) — кратчайший путь из v до конца: на конечной вершине ноль, иначе минимум по рёбрам из «вес плюс кратчайший путь из соседа». g.get(v, []) отдаёт пустой список для тупика, и минимум остаётся бесконечностью — через тупик пути нет. Проверка v == FINISH стоит первой, поэтому ребро 100 → 12 никогда не рассматривается. Недостижимые вершины вроде 6 функция просто не посещает.
Кеш @lru_cache обязателен: число вызовов без него равно числу путей, а их в демо больше двух миллиардов — рекурсия не досчитает. С кешем каждая вершина считается один раз.
Функция paths(v) отличается двумя строками: на конце единица вместо нуля, сумма вместо минимума. На демо-файле кратчайший путь ровно 10971, а путей 2 033 652 335.
Ещё один пример: три вопроса к одному файлу
Файл из восьми строк:
1 2 3.5
1 3 2.0
2 4 1.5
3 4 4.0
3 100 7.2
4 100 2.9
100 5 1.0
6 1 2.0
Пути из 1 в 100: 1 → 2 → 4 → 100 длиной 3.5 + 1.5 + 2.9 = 7.9; 1 → 3 → 100 длиной 9.2; 1 → 3 → 4 → 100 длиной 8.9. Ребро 100 → 5 ведёт из конца наружу, вершина 6 недостижима из 1 — обе ловушки на месте.
| Вопрос | Ответ |
|---|---|
| Целая часть длины кратчайшего пути | 7 (от 7.9) |
| Количество различных путей | 3 |
| Целая часть длины самого длинного пути | 9 (от 9.2) |
Код из раздела выше на этом файле печатает 7 и 3; для самого длинного пути в short меняют минимум на максимум и INF на -INF.
Вариации вопроса
| Вопрос | Что менять |
|---|---|
| Целая часть длины кратчайшего пути | int(short(START)) — демо |
| Количество различных путей | paths(START) |
| Целая часть длины самого длинного пути | в short максимум вместо минимума, старт с -INF |
| Путь через обязательную вершину M | кратчайший из 1 в M плюс кратчайший из M в 100 — два расчёта с разным концом: передавай конец параметром (short(v, finish)) или вызывай short.cache_clear() между расчётами — кеш помнит ответы для прежнего конца; число путей — произведение |
| Другие начало и конец | подставить в START и FINISH |
Для самого длинного пути тупики опасны вдвойне: из тупика конец недостижим, и максимум из пустого списка должен остаться минус бесконечностью, а не нулём. Через обязательную вершину задачу делят надвое, как обязательную точку в задании 13.
Альтернатива: Дейкстра
Для кратчайшего пути годится и алгоритм Дейкстры через heapq: очередь с приоритетом по расстоянию, вершина извлекается, расстояния до соседей обновляются. На 200 рёбрах он не быстрее рекурсии, но полезен, если граф вдруг не ациклический. Количество путей Дейкстра не считает — для него нужна рекурсия или топологический порядок. Общая идея «ответ для вершины зависит от ответов соседей» — это динамическое программирование, и оно же работает в заданиях 13 и 18.
Типичные ошибки
Нет g.get(v, [])
Тупик — вершина без ключа в словаре. g[v] падает с KeyError на первом же тупике. В файле демо тупиков нет — без исходящих рёбер там только конечная вершина, — но в типовом примере условия и в других файлах они бывают.
Рекурсия не останавливается на конце
Если проверять v == FINISH после перебора рёбер, функция уйдёт по ребру 100 → 12 и ответ изменится. Проверка — первая строка функции.
Вес прочитан как int
int("5.5") — ошибка. Вес всегда float.
Округление вместо целой части
round(7.5) — это 8, целая часть 7.5 — 7. В ответ идёт int.
Без кеша
Рекурсия без @lru_cache на демо не закончится: вызовов столько же, сколько путей. Кеш — не оптимизация, а условие работы.
Подборка ошибок по всем номерам — в статье Типичные ошибки на ЕГЭ по информатике.
Тайминг на экзамене
| Этап | Время |
|---|---|
| Прочитать условие: начало, конец, вид вопроса | 1 мин |
| Набрать чтение файла и функцию с кешем | 3 мин |
| Проверить на типовом примере (7, 3, 12) | 2 мин |
| Запустить на файле, записать целую часть | 1 мин |
| Итого | 7 мин |
Спецификация отводит двенадцать минут — запас на проверку есть, и тратить его стоит именно на типовой пример.
Как тренироваться
- Набери шаблон по памяти три раза и каждый раз проверь на типовом примере из условия — три числа 7, 3 и 12.
- Реши пять заданий на кратчайший путь и три на количество путей — файлы с тупиками и недостижимыми вершинами.
- Одно задание реши Дейкстрой и сравни с рекурсией.
- Нарисуй граф из 6–8 вершин на бумаге и посчитай пути руками — так становится видно, почему кеш обязателен.
Как изменились остальные номера — в обзоре ЕГЭ по информатике 2027: что изменилось; демозадание в контексте варианта — в разборе демоверсии 2027. Чтение файлов и словари, на которых держится код, — в разборе задания 17; графы без файла, по картинке и таблице, — задание 1.
Короткий итог
Задание 23 в 2027 году — ациклический граф из текстового файла. Словарь рёбер, рекурсия с кешем: ноль на конце и минимум по рёбрам для кратчайшего пути, единица и сумма — для числа путей. g.get(v, []) для тупиков, проверка конца первой строкой, float для весов и int для ответа. На демо — 10971.
Задания 23 в форме 2027 года с автопроверкой есть в TuteMe: кратчайший путь, самый длинный путь и число путей, а в файлах есть тупики, до которых можно дойти от начальной вершины.