Problem p02949 (python)

Fixed submission:
n, m, p = map(int, input().split())
abc = []
for _ in range(m):
    a, b, c = map(int, input().split())
    abc.append([a-1, b-1, p-c])

d = [float('inf')] * n
d[0] = 0

for i in range(n):
    for a, b, c in abc:
        d[b] = min(d[b], d[a] + c)

for a, b, c in abc:
    if d[b] > d[a] + c:
        d[b] = - float('inf')

for i in range(n):
    for a, b, c in abc:
        d[b] = min(d[b], d[a] + c)

if d[n-1] == - float('inf'):
    print(-1)
else:
    print(max(0, - d[n-1]))

Buggy submission (verdict: Runtime Error):
class BellmanFord():
    class Edge():
        def __init__(self, _from, _to, _cost):
            self.from_ = _from
            self.to = _to
            self.cost = _cost

    def __init__(self):
        self.edges = []  # 辺
        self.v_set = set()  # 頂点の集合

    @property
    def E(self):
        return len(self.edges)

    @property
    def V(self):
        return len(self.v_set)

    def add(self, _from, _to, _cost):
        self.edges.append(self.Edge(_from, _to, _cost))
        self.v_set.add(_from)
        self.v_set.add(_to)

    def shortest_path(self, s):
        d = [float("inf")] * self.V
        d[s] = 0

        while True:
            do_update = False
            for i in range(self.E):
                e = self.edges[i]
                if d[e.from_] != float("inf") and d[e.to] > d[e.from_] + e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    do_update = True

            if not do_update: break

        return d

    def exist_negative_loop(self):
        d = [0] * self.V
        for i in range(self.V):
            for j in range(self.E):
                e = self.edges[j]
                if d[e.to] > d[e.from_] + e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    if i == self.V - 1: return True
        return False

n, m, p = map(int, input().split())
abc = []
e = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    abc.append([a-1, b-1, p-c])
    e[a-1].append(b-1)

v = [0] * n
v[0] = 1
def bfs(x, depth):
    #print(x, depth, e[x])
    if depth >= n:
        return 1
    if x == n-1:
        return 0
    temp = 1
    for y in e[x]:
        #print(y)
        if v[y] == 1 or x == y:
            continue
        #print(x, y)
        ret = bfs(y, depth + 1)
        if ret == 0:
            v[y] = 1
            temp = 0
    return temp

bfs(0, 0)
x = 1
for i in range(n):
    if v[i] == 1:
        v[i] = x
        x += 1

bf = BellmanFord()
for a, b, c in abc:
    if v[a]!= 0 and v[b] != 0:
        bf.add(v[a]-1, v[b]-1, c)

if bf.exist_negative_loop():
    print(-1)
    exit()
else:
    print(max(0, - bf.shortest_path(0)[-1]))

Buggy submission (verdict: Runtime Error):
class BellmanFord():
    class Edge():
        def __init__(self, _from, _to, _cost):
            self.from_ = _from
            self.to = _to
            self.cost = _cost

    def __init__(self):
        self.edges = []  # 辺
        self.v_set = set()  # 頂点の集合

    @property
    def E(self):
        return len(self.edges)

    @property
    def V(self):
        return len(self.v_set)

    def add(self, _from, _to, _cost):
        self.edges.append(self.Edge(_from, _to, _cost))
        self.v_set.add(_from)
        self.v_set.add(_to)

    def shortest_path(self, s):
        d = [float("inf")] * self.V
        d[s] = 0

        while True:
            do_update = False
            for i in range(self.E):
                e = self.edges[i]
                if d[e.from_] != float("inf") and d[e.to] > d[e.from_] + e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    do_update = True

            if not do_update: break

        return d

    def exist_negative_loop(self):
        d = [0] * self.V
        for i in range(self.V):
            for j in range(self.E):
                e = self.edges[j]
                if d[e.to] > d[e.from_] + e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    if i == self.V - 1: return True
        return False

n, m, p = map(int, input().split())
abc = []
e = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    abc.append([a-1, b-1, p-c])
    e[a-1].append(b-1)

v = [0] * n
v[0] = 1
def bfs(x, depth):
    #print(x, depth, e[x])
    if depth >= n:
        return 1
    if x == n-1:
        return 0
    temp = 1
    for y in e[x]:
        #print(y)
        if v[y] == 1 or x == y:
            continue
        #print(x, y)
        ret = bfs(y, depth + 1)
        if ret == 0:
            v[y] = 1
            temp = 0
    return temp

bfs(0, 0)

bf = BellmanFord()
for a, b, c in abc:
    if v[a] * v[b] == 1:
        bf.add(a, b, c)
    else:
        bf.add(a, b, float('inf'))

if bf.exist_negative_loop():
    print(-1)
    exit()
else:
    print(max(0, - bf.shortest_path(0)[-1]))

Buggy submission (verdict: Runtime Error):
class BellmanFord():
    class Edge():
        def __init__(self, _from, _to, _cost):
            self.from_ = _from
            self.to = _to
            self.cost = _cost

    def __init__(self):
        self.edges = []  # 辺
        self.v_set = set()  # 頂点の集合

    @property
    def E(self):
        return len(self.edges)

    @property
    def V(self):
        return len(self.v_set)

    def add(self, _from, _to, _cost):
        self.edges.append(self.Edge(_from, _to, _cost))
        self.v_set.add(_from)
        self.v_set.add(_to)

    def shortest_path(self, s):
        d = [float("inf")] * self.V
        d[s] = 0

        while True:
            do_update = False
            for i in range(self.E):
                e = self.edges[i]
                if d[e.from_] != float("inf") and d[e.to] > d[e.from_] + e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    do_update = True

            if not do_update: break

        return d

    def exist_negative_loop(self):
        d = [0] * self.V
        for i in range(self.V):
            for j in range(self.E):
                e = self.edges[j]
                if d[e.to] > d[e.from_] + e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    if i == self.V - 1: return True
        return False

n, m, p = map(int, input().split())
abc = []
e = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    abc.append([a-1, b-1, p-c])
    e[a-1].append(b-1)

v = [0] * n
v[0] = 1
def bfs(x, depth):
    #print(x, depth, e[x])
    if depth >= n:
        return 1
    if x == n-1:
        return 0
    temp = 1
    for y in e[x]:
        #print(y)
        if v[y] == 1 or x == y:
            continue
        #print(x, y)
        ret = bfs(y, depth + 1)
        if ret == 0:
            v[y] = 1
            temp = 0
    return temp

bfs(0, 0)

bf = BellmanFord()
for a, b, c in abc:
    if v[a] * v[b] == 1:
        bf.add(a, b, c)
    else:
        bf.add(a, b, float('inf'))

if bf.exist_negative_loop():
    print(-1)
    exit()
else:
    print(max(0, - bf.shortest_path(0)[-1]))