Задание 23 демоверсии ЕГЭ 2027 по информатике: разбор

Графы: кратчайший путь. Реши сам, потом открой решение.

Задание 23

Задание выполняется с использованием прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа ( $L$ , $M$ ) и одно положительное вещественное число ( $W$ ). $L$ и $M$ – номера вершин графа, $W$ – вес ребра, ведущего из вершины $L$ в вершину $M$ . Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.

Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L \le 1000$ , $M \le 1000$ ; $W \le 10\,000$ . Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле для графа на рисунке

Ориентированный граф: 6→7 (7.0), 6→1 (1.0), 1→7 (5.5), 7→100 (2.0), 1→100 (12.0), 1→4 (2.5), 4→100 (8.0), 100→12 (1.0)

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.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Файл к заданию 23

Источник: ФИПИ, проект демоверсии ЕГЭ 2027, с. 20

Решение и ответ

Веса положительные, поэтому подходит алгоритм Дейкстры с очередью: всегда раскрываем ближайшую ещё не обработанную вершину.
split() без аргументов съедает любые пробелы и табуляции, пустые строки пропускаем.

import heapq

g = {}
for s in open('23.txt'):
    if s.split():
        l, m, w = s.split()
        g.setdefault(int(l), []).append((int(m), float(w)))

d = {1: 0}
q = [(0, 1)]
while q:
    x, v = heapq.heappop(q)
    if x > d[v]:
        continue
    for u, w in g.get(v, []):
        if x + w < d.get(u, float('inf')):
            d[u] = x + w
            heapq.heappush(q, (x + w, u))
print(int(d[100]))

Длина кратчайшего пути до вершины 100 — 10971 с дробной частью, целая часть 10971.

Ответ: 10971