Problem p03722 (python)

Fixed submission:
N, M = map(int, input().split())


class BellmanFord(object):
    def __init__(self, edges, n_nodes, start):
        self.edges = edges
        dist = [float('inf')] * n_nodes
        dist[start] = 0
        prev = [None] * n_nodes

        for _ in range(n_nodes - 1):
            for u, v, weight in edges:
                if dist[u] == float('inf'):
                    continue
                if dist[v] > dist[u] + weight:
                    dist[v] = dist[u] + weight
                    prev[v] = u
        self.dist = dist
        self.prev = prev

    def check(self, goal=None):
        if goal is None:
            for u, v, weight in self.edges:
                if self.dist[v] > self.dist[u] + weight:
                    return False
            return True
        else:
            negative = [False] * N
            for _ in range(N):
                for u, v, weight in self.edges:
                    if self.dist[u] == float('inf'):
                        continue
                    if negative[u] or self.dist[v] > self.dist[u] + weight:
                        negative[v] = True
            return not negative[goal]


edges = [None] * M
for i in range(M):
    a, b, c = map(int, input().split())
    edges[i] = (a - 1, b - 1, -c)

bf = BellmanFord(edges, N, 0)
if bf.check(N - 1):
    print(-bf.dist[N - 1])
else:
    print('inf')

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

N, M = map(int, input().split())


class Graph(object):
    def __init__(self):
        self.edges = defaultdict(list)
        self.nodes = set()

    def add_edge(self, src, dst, weight=1):
        self.edges[src].append((dst, weight))
        self.nodes.add(src)
        self.nodes.add(dst)


def bellman_ford(graph, start):
    N = len(graph.nodes)
    dist = [int(1e18)] * N
    dist[start] = 0
    prev = [None] * N

    for _ in range(N - 1):
        for u, l in graph.edges.items():
            for v, weight in l:
                if dist[v] > dist[u] + weight:
                    dist[v] = dist[u] + weight
                    prev[v] = u
    
    for u, l in graph.edges.items():
        for v, weight in l:
             if dist[u] + weight < dist[v]:
                 return False
    return dist


g = Graph()
for _ in range(M):
    a, b, c = map(int, input().split())
    g.add_edge(a - 1, b - 1, -c)

dist = bellman_ford(g, 0)
if dist:
    print(-dist[N - 1])
else:
    print('inf')

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
from heapq import heappop, heappush

N, M = map(int, input().split())


class Graph(object):
    def __init__(self):
        self.edges = defaultdict(list)
        self.nodes = set()

    def add_edge(self, src, dst, weight=1):
        self.edges[src].append((dst, weight))
        self.nodes.add(src)
        self.nodes.add(dst)


def BellmanFord(graph, start):
    N = len(graph.nodes)
    dist = [float('inf')] * N
    dist[start] = 0
    prev = [None] * N

    for _ in range(N - 1):
        for u, l in graph.edges.items():
            for v, weight in l:
                if dist[v] > dist[u] + weight:
                    dist[v] = dist[u] + weight
                    prev[v] = u
    
    for u, l in graph.edges.items():
        for v, weight in l:
             if dist[u] + weight < dist[v]:
                 return False
    return dist


g = Graph()
for _ in range(M):
    a, b, c = map(int, input().split())
    g.add_edge(a - 1, b - 1, -c)

dist = BellmanFord(g, 0)
if dist:
    print(-dist[N - 1])
else:
    print('inf')

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
from heapq import heappop, heappush

N, M = map(int, input().split())


class Graph(object):
    def __init__(self):
        self.edges = defaultdict(list)
        self.nodes = set()

    def add_edge(self, src, dst, weight=1):
        self.edges[src].append((dst, weight))
        self.nodes.add(src)
        self.nodes.add(dst)


def BellmanFord(graph, start):
    N = len(graph.nodes)
    dist = [float('-inf')] * N
    dist[start] = 0
    prev = [None] * N

    for _ in range(N - 1):
        for u, l in graph.edges.items():
            for v, weight in l:
                if dist[v] < dist[u] + weight:
                    dist[v] = dist[u] + weight
                    prev[v] = u
    
    for u, l in graph.edges.items():
        for v, weight in l:
             if dist[u] + weight > dist[v]:
                 return False
    return dist


g = Graph()
for _ in range(M):
    a, b, c = map(int, input().split())
    g.add_edge(a - 1, b - 1, c)

dist = BellmanFord(g, 0)
if dist:
    print(dist[N - 1])
else:
    print('inf')

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
from heapq import heappop, heappush

N, M = map(int, input().split())


class Graph(object):
    def __init__(self):
        self.edges = defaultdict(list)
        self.nodes = set()

    def add_edge(self, src, dst, weight=1):
        self.edges[src].append((dst, weight))
        self.nodes.add(src)
        self.nodes.add(dst)


def BellmanFord(graph, start):
    N = len(graph.nodes)
    dist = [float('-inf')] * N
    dist[start] = 0
    prev = [None] * N

    for _ in range(N):
        for u, l in graph.edges.items():
            for v, weight in l:
                if dist[v] < dist[u] + weight:
                    dist[v] = dist[u] + weight
                    prev[v] = u
    
    for u, l in graph.edges.items():
        for v, weight in l:
             if dist[u] + weight > dist[v]:
                 return False
    return dist


def topological_sort(graph):
    g = graph.edges
    N = len(graph.nodes)

    indeg = [0] * N
    for v in g:
        for u, _ in g[v]:
            indeg[u] += 1

    S = [i for i in range(N) if indeg[i] == 0]
    L = []

    while S:
        u = S.pop()
        L.append(u)
        for v, _ in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                S.append(v)
    return L


g = Graph()
for _ in range(M):
    a, b, c = map(int, input().split())
    g.add_edge(a - 1, b - 1, c)

if len(topological_sort(g)) == N:
    dist = BellmanFord(g, 0)
    if dist:
        print(dist[N - 1])
    else:
        print('inf')
else:
    print('inf')

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
from heapq import heappop, heappush

N, M = map(int, input().split())


class Graph(object):
    def __init__(self):
        self.edges = defaultdict(list)
        self.nodes = set()

    def add_edge(self, src, dst, weight=1):
        self.edges[src].append((dst, weight))
        self.nodes.add(src)
        self.nodes.add(dst)


def BellmanFord(graph, start):
    N = len(graph.nodes)
    dist = [float('-inf')] * N
    dist[start] = 0
    prev = [None] * N

    for _ in range(N):
        for u, l in graph.edges.items():
            for v, weight in l:
                if dist[v] < dist[u] + weight:
                    dist[v] = dist[u] + weight
                    prev[v] = u
    return dist


def topological_sort(graph):
    g = graph.edges
    N = len(graph.nodes)

    indeg = [0] * N
    for v in g:
        for u, _ in g[v]:
            indeg[u] += 1

    S = [i for i in range(N) if indeg[i] == 0]
    L = []

    while S:
        u = S.pop()
        L.append(u)
        for v, _ in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                S.append(v)
    return L


g = Graph()
for _ in range(M):
    a, b, c = map(int, input().split())
    g.add_edge(a - 1, b - 1, c)

if len(topological_sort(g)) == N:
    dist = BellmanFord(g, 0)
    print(dist[N - 1])
else:
    print('inf')

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
from heapq import heappop, heappush

N, M = map(int, input().split())


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)
        self.nodes = set()

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))
        self.nodes.add(src)
        self.nodes.add(dst)

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        g = graph.graph

        self.dist = defaultdict(lambda: float('-inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] > dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] < alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]


def topological_sort(graph):
    g = graph.graph
    N = len(graph.nodes)

    indeg = [0] * N
    for v in g:
        for u, _ in g[v]:
            indeg[u] += 1

    S = [i for i in range(N) if indeg[i] == 0]
    L = []

    while S:
        u = S.pop()
        L.append(u)
        for v, _ in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                S.append(v)
    return L


g = Graph()
for _ in range(M):
    a, b, c = map(int, input().split())
    g.add_edge(a - 1, b - 1, c)

if len(topological_sort(g)) == N:
    d = Dijkstra(g, 0)
    print(d.shortest_distance(N - 1))
else:
    print('inf')