Что неверного в этой функции для нахождения самого длинного пути между двумя узлами во взвешенной группе доступности баз данных?

Question

Я работаю над заданием, в котором мне дана вершина n, гарантированно являющаяся исходной вершиной и имеющая наименьшую целочисленную метку в (направленном ациклическом) графе, вершину m, гарантированно являющуюся вершиной-приемником, инаибольшая целочисленная метка и e <= 100 ребер u-> v: w, представляющих направленное ребро из вершины u в вершину v с весом w.Ожидается, что мой код выведет две строки, первая из которых содержит общий вес самого длинного пути между вершинами n и m в группе обеспечения доступности баз данных, а вторая содержит целочисленные метки для вершин в этом пути, n-> v ₀ -> v ₁ -> ...-> м.Если существует несколько путей одинакового веса, мы можем вывести любой из них.

Мой код выводит правильный ответ для всех примеров тестовых примеров, приведенных с оператором задачи, несколько дополнительных тестовых случаев I 'созданный во время отладки, и все, кроме одного из частных тестовых случаев, с которыми мой код запускается через онлайн-грейдер, который я должен отправить.Грейдер не предоставляет тестовые входные данные, с которыми он проверяет ваш код, он просто дает вам двоичный тест или неудачу, а также тестовые случаи, на которые ваш код дал неправильный ответ.

Мой код только когда-либо был неудачнымпоследний из 8 частных тестовых примеров от онлайн-грейдера, но из-за того, что грейдер не предоставляет фактические входные данные, мне трудно понять, где проблема.Была проблема с моим исходным кодом, из-за которой он возвращал самый длинный путь в группе обеспечения доступности баз данных, начиная с любой вершины и заканчивая приемником, и не обязательно самый длинный путь, начиная с желаемой исходной вершины, но с тех пор я написалпара тестов и исправили эту проблему (если я что-то упустил), и это, по-видимому, не причина моего кода.Более новая реализация все еще терпит неудачу на заключительном тесте.С тех пор я не мог самостоятельно выдвигать какие-либо неудачные случаи.Мой код выглядит следующим образом:

import math
import re
import sys


class Node:
    def __init__(self):
        self.incoming_edges = []
        self.path = []
        self.weight = -math.inf

def find_longest_path(source, own):
    for edge in graph[own].incoming_edges:
        find_longest_path(source, edge[0])

    if len(graph[own].incoming_edges) > 0:
        heaviest_edge = None
        edge_weight = -math.inf

        for edge in graph[own].incoming_edges:
            if graph[edge[0]].weight + edge[1] > edge_weight:
                edge_weight = graph[edge[0]].weight + edge[1]
                heaviest_edge = edge[0]

        if heaviest_edge != None:
            graph[own].weight = edge_weight
            graph[own].path = graph[heaviest_edge].path + [own]

    elif own == source:
        graph[own].weight = 0
        graph[own].path = [own]


if __name__ == "__main__":
    source = int(sys.stdin.readline().strip())
    sink = int(sys.stdin.readline().strip())
    graph = [Node() for _ in range(sink + 1)]
    for edge in [list(map(int, re.split('->|:', line.strip()))) for line in sys.stdin]:
        graph[edge[1]].incoming_edges.append((edge[0], edge[2]))
    find_longest_path(source, sink)
    print(graph[sink].weight if graph[sink].weight >= 0 else '')
    print('->'.join(list(map(str, graph[sink].path))))

Если кто-то может указать, где это идет не так, или, по крайней мере, предоставить тестовый ввод, который возвращает неправильный ответ, это будет очень цениться.

Кроме того, я знаю, что мой код потенциально пересчитывает кучу вещей без необходимости.В моей первоначальной реализации была проверка для этого, которую я удалил во время отладки ранее, и я добавлю что-то подобное обратно, как только получу эту работу.