Задание №23: Графы и алгоритмы
Основные типы и прототипы задания №23:
Поиск маршрутов в графе
Кратчайшие пути
Алгоритмический анализ графов
Условие задания
В текстовом файле 23-1.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вершин графа, W – вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь. Вершины графа могут быть пронумерованы не подряд. L ≤ 1000, M ≤ 1000; W ≤ 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100, состоящего не более чем из 6 рёбер. Существование хотя бы одного такого пути гарантируется.
Типовой пример организации данных в файле для графа, показанного на рисунке:
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100, состоящего не более чем из 6 рёбер. Существование хотя бы одного такого пути гарантируется.
Типовой пример организации данных в файле для графа, показанного на рисунке:
100 12 1.0Для приведённого примера верным ответом будет 7.
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
Ответ:
20198
Решение на 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))
Этот код разобран по шагам в разборе задания №23: там же типичные ошибки и лайфхаки.