Задание 23 ЕГЭ: число рёбер в пути

Число рёбер в пути. Тема номера — кратчайший путь во взвешенном графе. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

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

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

Определите наименьшее количество рёбер в пути из вершины с номером 629 в вершину с номером 873. Существование хотя бы одного пути гарантируется.

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

Вершины графа могут быть пронумерованы не подряд. 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

Для приведённого примера при таком же вопросе о путях из вершины 1 в вершину 100 верным ответом будет 1.

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

Скачать файл к примеру

Решение

Число рёбер — это длина пути, если считать вес каждого ребра равным 1. Рекурсия: fewest(v) = 1 + минимум fewest(u) по рёбрам v → u (подошёл бы и поиск в ширину).

Ответ: 8.

from collections import defaultdict
from functools import lru_cache

g = defaultdict(list)                  # g[L] — список (M, W)
for line in open("23.txt"):
    p = line.split()                   # split() без аргументов: любые пробелы и табуляции
    if p:
        g[int(p[0])].append((int(p[1]), float(p[2])))

@lru_cache(None)
def fewest(v, t):                      # наименьшее число рёбер в пути из v в t
    if v == t:
        return 0
    return min((1 + fewest(u, t) for u, w in g[v]), default=float("inf"))

print(fewest(629, 873))

Решить такую задачу — новый вариант с проверкой