23. Алгоритмические задачи, связанные с анализом графов: #313079

В текстовом файле содержится описание ациклического ориентированного взвешенного графа.

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

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

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

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

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

Для приведённого примера при условии «ровно из $2$ рёбер» верным ответом будет $2$ (пути $1–7–100$ и $1–4–100$); путь ровно из одного ребра один ($1–100$), путей из трёх и более рёбер нет.

from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {}                                   # вершина -> список соседей
for line in open('23_8.txt'):
    s = line.split()
    if len(s) < 3:
        continue
    a, b = int(s[0]), int(s[1])          # вес ребра не нужен
    g.setdefault(a, []).append(b)
N = 8
@lru_cache(None)
def f(v, k):                             # число путей v -> 100 ровно из k рёбер
    if k == 0:
        return 1 if v == 100 else 0
    if v == 100:                         # в вершине 100 путь заканчивается
        return 0
    return sum(f(u, k - 1) for u in g.get(v, []))
print(f(1, N))