Программа с @cache

Как превратить строки файла в граф, по которому можно ходить?

Разложить рёбра по начальным вершинам в словарь: ключ — вершина, значение — список пар (куда, вес). Тогда все стрелки из вершины v — это graph[v].

Каждую строку разбиваем line.split(): без аргумента он делит по любым пробелам и табуляциям, сколько бы их ни было. Получаются три куска текста. Номера вершин превращаем в int, вес — в float: он дробный. Заголовка в файле нет — первая строка тоже ребро.

graph = {}for line in open("23.txt"):    a, b, w = line.split()    a, b, w = int(a), int(b), float(w)    if a not in graph:        graph[a] = []    graph[a].append((b, w)) print(graph[1])print(graph.get(12, []))

Посмотри, как словарь растёт строка за строкой учебного файла:

Из 12 стрелок нет, поэтому и ключа 12 в словаре нет. graph[12] остановил бы программу ошибкой KeyError, а graph.get(12, []) возвращает пустой список — для тупика это и нужно.

Как записать правило для f на Python?

Почти дословно: в цели вернуть 0, иначе перебрать стрелки из v и взять наименьшее «вес + f(конца)». Функция вызывает сама себя для соседей — это рекурсия. Словарь graph уже прочитан из файла, как в разделе выше; cache подключаем первой строкой программы.

from functools import cache  @cachedef f(v):    if v == 100:        return 0    best = float("inf")    for u, w in graph.get(v, []):        best = min(best, w + f(u))    return best  print(f(1), f(6), f(12))

Разберём функцию по строкам:

• if v == 100: return 0 — мы в цели, идти больше некуда.
• best = float("inf") — пока ни одного пути до цели не найдено: бесконечность.
• for u, w in graph.get(v, []) — каждая стрелка v → u весом w. У тупика список пуст, цикл не выполнится, и функция вернёт бесконечность — как в подтеме 2.
• best = min(best, w + f(u)) — шаг по стрелке плюс лучший остаток пути от u.

Руками мы считали от цели назад, а функция начинает с другого конца: f(1) просит f(7), та — f(100). Ответы возвращаются по цепочке обратно. Посмотри по шагам; внизу — стек вызовов: функции, которые начали работу и ждут ответа.

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

Что будет, если убрать строку @cache?

Ответ тот же, но одни и те же вершины будут считаться снова и снова. @cache запоминает ответ для каждой вершины, и второй раз он берётся из памяти. В учебном графе f(7) нужна дважды: из 6 и из 1. Без запоминания второй раз она пройдёт свой путь заново:

На восьми рёбрах разница мала. Но в файле задачи темы без @cache функция была бы вызвана почти триллион раз: она прошла бы по каждому из 150 миллиардов путей. Программа не закончит и за сутки. С @cache каждая из 59 вершин, до которых можно дойти из 1, считается один раз.

cache берут из модуля functools: первая строка программы — from functools import cache, а @cache ставят прямо над def.

Решим задачу темы целиком:

«В текстовом файле 23-5.txt содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром. Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь. Вершины графа могут быть пронумерованы не подряд. L ≤ 1000, M ≤ 1000; W ≤ 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.»

Программа та же, меняется только имя файла и последняя строка: ответ — целая часть f(1). Файл 23-5.txt приложен к задаче темы в практике этой подтемы — сохрани его рядом с программой.

from functools import cache graph = {}for line in open("23-5.txt"):    a, b, w = line.split()    a, b, w = int(a), int(b), float(w)    if a not in graph:        graph[a] = []    graph[a].append((b, w))  @cachedef f(v):    if v == 100:        return 0    best = float("inf")    for u, w in graph.get(v, []):        best = min(best, w + f(u))    return best  print(f(1))print(int(f(1)))

Ответ — 10211. Посмотри на первую строку вывода: 10211.630000000003 вместо 10211.63. Дроби в float хранятся приближённо, и при сложении копятся крошечные ошибки. На целую часть они не влияют, пока сумма не стоит вплотную к целому числу.

• Графсловарь: вершина → список пар (куда, вес)
• Строка файлаline.split(); номера — int, вес — float
• Тупикgraph.get(v, []) — пустой список, f = ∞
• f(v)в цели 0, иначе min(w + f(u)) по стрелкам из v
• @cacheкаждая вершина считается один раз
• Ответint(f(1)) — в самом конце, не round
• Задача темы10211