Задача #4418
Обход графа
(Л. Шастин) В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вершин графа, W – вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Некоторые вершины графа являются «тупиками» — из них не выходит ни одного ребра. Найдите и запишите в ответе целую часть максимальной длины пути из вершины с номером 2027 до какого-либо из достижимых «тупиков» графа. Под максимальной длиной пути понимается максимальная сумма весов рёбер, составляющих путь. Гарантируется, что хотя бы для одного «тупика» такой путь существует.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. L ≤ 10000, M ≤ 10000; W ≤ 100. Количество строк в файле не превосходит 100 000. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Типовой пример организации данных во входном файле для графа на рисунке.
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
Для приведённого примера в графе только вершина №12 является «тупиком». При старте из вершины №6 ответом будет 14.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла
Решение
Ответ
from functools import *
@cache
def f(u):
if u not in g: return 0
return max([f(v) + w for v, w in g.get(u, [])] + [float('-inf')])
g = {}
for l in open('23_4418.txt'):
u, v, w = l.split()
g.setdefault(int(u), []).append((int(v), float(w)))
print(int(f(2027)))