Problem p03722 (python)

Fixed submission:
class BellmanFord():
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, start, numNodes):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = [float('inf') for i in range(self.N)]
        d[start] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1 and e[1] == numNodes-1:
                        return True, d
        return False, d


N, M = map(int, input().split())
graph = BellmanFord(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -c, directed=True)

hasNegativeCycle, d = graph.BellmanFord_negative_bool(0, N)
if hasNegativeCycle:
    print('inf')
else:
    print(-1 * d[N-1])

Buggy submission (verdict: Runtime Error):
class BellmanFord():
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_search(self, start):
        # true, dist なら負の経路を含む
        d = collections.defaultdict(lambda: float('inf'))
        d[start] = 0
        counter = 0
        while True:
            update = False
            for n in range(N):
                for edge in self.edges[n]:
                    to, cost = edge
                    if d[n] != float('inf') and d[to] > d[n] + cost:
                        d[to] = d[n] + cost
                        update = True
                        counter += 1
            if not update:
                break
            if counter >= self.N ** 2:
                return True, d

        return False, d


N, M = map(int, input().split())
graph = BellmanFord(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -c, directed=True)

hasNegativeCycle, d = graph.BellmanFord_negative_search(0)
if hasNegativeCycle:
    print('inf')
else:
    print(-1 * d[N-1])

Buggy submission (verdict: Runtime Error):
class BellmanFord():
    def __init__(self, N):
        self.N = N
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        :param s: 始点
        :return: d[i] 始点sから各点iまでの最短経路
        """
        d = [float('inf') for i in range(self.N)]
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_search(self, start):
        # true, dist なら負の経路を含む
        d = collections.defaultdict(lambda: float('inf'))
        d[start] = 0
        counter = 0
        while True:
            update = False
            for n in range(N):
                for edge in self.edges[n]:
                    to, cost = edge
                    if d[n] != float('inf') and d[to] > d[n] + cost:
                        d[to] = d[n] + cost
                        update = True
                        counter += 1
            if not update:
                break
            if counter >= self.N ** 2:
                return True, d

        return False, d


N, M = map(int, input().split())
graph = BellmanFord(N)
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, -c, directed=True)

hasNegativeCycle, d = graph.BellmanFord_negative_bool(0, N)
if hasNegativeCycle:
    print('inf')
else:
    print(-1 * d[N-1])