Задание 23 ЕГЭ: количество путей

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

Пример

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

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

Определите количество различных путей из вершины с номером 140 в вершину с номером 469, проходящих через вершину с номером 839. Существование хотя бы одного такого пути гарантируется.

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

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

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

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

Решение

Правило умножения: каждый путь через вершину v — это путь из начала в v, продолженный путём из v в конец. Количество путей из вершины в вершину считаем рекурсией с запоминанием. Получается 15.

Ответ: 15.

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 paths(v, t):                       # количество путей из v в t
    if v == t:
        return 1
    return sum(paths(u, t) for u, w in g[v])

print(paths(140, 839) * paths(839, 469))

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