Problem p03722 (python)

Fixed submission:
n, m = map(int, input().split())

edges = []
for i in range(m):
    a, b, w = map(int, input().split())
    edges.append((a-1, b-1, w))

init_val = -10 ** 9 * 1000
d = [init_val] * n
d[0] = 0
for _ in range(n):
    updated = False
    for a, b, w in edges:
        if d[a] != init_val and d[b] < d[a] + w:
            d[b] = d[a] + w
            updated = True
    if not updated:
        break
if updated: #閉路の存在
     for a, b, w in edges:
        if d[a] != init_val and d[b] < d[a] + w:
            d[b] = d[a] + w
            if b == n - 1:
                print('inf')
                quit()
print(d[n-1])

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

def fast_bellman_ford(n, s, graph, edge_n, init_val): #どう？
    d = [init_val] * n
    d[s] = 0
    q = deque([s])
    checker = [-1] * n
    for i in range(n):
        m = len(q)
        for _ in range(m):
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    if checker[vt] < i:
                        q.append(vt)
                        checker[vt] = i
        if not q:
            break
    if q: #閉路の存在
        minus_inf = -float('inf')
        i += 1
        while q:
            m = q.count
            for _ in range(m):
                vf = q.popleft()
                for vt, w in graph[vf]:
                    if d[vt] > d[vf] + w:
                        d[vt] = minus_inf
                        if checker[vt] < i:
                            q.append(vt)
                            checker[vt] = i
            i += 1
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = fast_bellman_ford(n, 0, graph, 2 * m, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Buggy submission (verdict: Runtime Error):
class FixedSizeQueue:
    def __init__(self, n, init_val):
        self.queue = [init_val] * n #根にサイズを負の値で格納する。
        self.l = 0
        self.r = 0
        self.n = n
        self.size = 0
    def append(self, val):
        if self.size == self.n:
            raise IndexError('fixed-size-queue is full')
        self.queue[self.r] = val
        self.r = (self.r + 1) % self.n
        self.size += 1

    def popleft(self):
        if self.size == 0:
            raise IndexError('dequeue from empty queue')
        val = self.queue[self.l]
        self.l = (self.l + 1) % self.n
        self.size -= 1
        return val

    def pop(self):
        if self.size == 0:
            raise IndexError('dequeue from empty queue')
        val = self.queue[self.r - 1]
        self.r = (self.r - 1) % self.n
        self.size -= 1
        return val
    
    def get_size(self):
        return self.size
    
    def __bool__(self):
        return self.size != 0

def fast_bellman_ford(n, s, graph, edge_n, init_val): #どう？
    d = [init_val] * n
    d[s] = 0
    q = FixedSizeQueue(edge_n, 0)
    q.append(s)
    for _ in range(n):
        m = q.get_size()
        for _ in range(m):
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    q.append(vt)
        if not q:
            break
    if q: #閉路の存在
        minus_inf = -float('inf')
        while q:
            m = q.get_size()
            for _ in range(m):
                vf = q.popleft()
                for vt, w in graph[vf]:
                    if d[vt] > d[vf] + w:
                        d[vt] = minus_inf
                        q.append(vt)
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = fast_bellman_ford(n, 0, graph, 2 * m, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Buggy submission (verdict: Runtime Error):
class FixedSizeQueue:
    def __init__(self, n, init_val):
        self.queue = [init_val] * n #根にサイズを負の値で格納する。
        self.l = 0
        self.r = 0
        self.n = n
        self.size = 0
    def append(self, val):
        if self.size == self.n:
            raise IndexError('fixed-size-queue is full')
        self.queue[self.r] = val
        self.r = (self.r + 1) % self.n
        self.size += 1

    def popleft(self):
        if self.size == 0:
            raise IndexError('dequeue from empty queue')
        val = self.queue[self.l]
        self.l = (self.l + 1) % self.n
        self.size -= 1
        return val

    def pop(self):
        if self.size == 0:
            raise IndexError('dequeue from empty queue')
        val = self.queue[self.r - 1]
        self.r = (self.r - 1) % self.n
        self.size -= 1
        return val
    
    def get_size(self):
        return self.size
    
    def __bool__(self):
        return self.size != 0

def fast_bellman_ford(n, s, graph, edge_n, init_val): #どう？
    d = [init_val] * n
    d[s] = 0
    q = FixedSizeQueue(edge_n, 0)
    q.append(s)
    for _ in range(n):
        m = q.get_size()
        for _ in range(m):
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    q.append(vt)
        if not q:
            break
    if q: #閉路の存在
        minus_inf = -float('inf')
        while q:
            m = q.get_size()
            for _ in range(m):
                vf = q.popleft()
                for vt, w in graph[vf]:
                    if d[vt] > d[vf] + w:
                        d[vt] = minus_inf
                        q.append(vt)
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = fast_bellman_ford(n, 0, graph, m, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')

Buggy submission (verdict: Runtime Error):
def moores_d(n, s, graph, init_val): 
    d = [init_val] * n
    d[s] = 0
    stack = [s]
    for _ in range(n):
        next_stack = []
        for _ in range(m):
            vf = stack.pop()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    next_stack.append(vt)
        stack = next_stack
        if not stack:
            break
    if stack: #閉路の存在
        minus_inf = -float('inf')
        next_stack = []
        while stack:
            vf = stack.pop()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = minus_inf
                    next_stack.append(vt)
            stack = next_stack
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = moores_d(n, 0, graph, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')