Problem p02949 (python)

Fixed submission:
# https://atcoder.jp/contests/abc137/tasks/abc137_e

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(1000000)

def main():
    n, m, p = map(int, input().split())
    edges = []
    graph = defaultdict(list)
    rev_graph = defaultdict(list)

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

    # pick up nodes on goal path
    reachable_from_start = [False] * n

    # print(edges)
    def dfs(node):
        if reachable_from_start[node]:
            return
        reachable_from_start[node] = True
        for next_node in graph[node]:
            dfs(next_node)

    reachable_to_end = [False] * n

    def rdfs(node):
        if reachable_to_end[node]:
            return
        reachable_to_end[node] = True
        for next_node in rev_graph[node]:
            rdfs(next_node)

    dfs(0)
    rdfs(n-1)

    valid = [False] * n
    for i in range(n):
        valid[i] = reachable_from_start[i] and reachable_to_end[i]

    inf = 10**10
    scores = [inf] * n
    scores[0] = 0
    loop = 0

    # bellman-ford
    updated = True
    while updated:
        updated = False
        for i in range(m):
            a, b, c = edges[i]
            if not valid[a]:
                continue
            if not valid[b]:
                continue

            new_cost = scores[a] + c
            if new_cost < scores[b]:
                updated = True
                scores[b] = new_cost

        loop += 1
        if loop > n:
            print(-1)
            return

    print(max(0, -scores[-1]))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc137/tasks/abc137_e

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10**10)

def main():
    n, m, p = map(int, input().split())
    edges = []
    graph = defaultdict(list)
    rev_graph = defaultdict(list)

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

    # pick up nodes on goal path
    reachable_from_start = [False] * n

    # print(edges)
    def dfs(node):
        if reachable_from_start[node]:
            return
        reachable_from_start[node] = True
        for next_node in graph[node]:
            dfs(next_node)

    reachable_to_end = [False] * n

    def rdfs(node):
        if reachable_to_end[node]:
            return
        reachable_to_end[node] = True
        for next_node in rev_graph[node]:
            rdfs(next_node)

    dfs(0)
    rdfs(n-1)

    valid = [False] * n
    for i in range(n):
        valid[i] = reachable_from_start[i] and reachable_to_end[i]

    inf = 10**10
    scores = [inf] * n
    scores[0] = 0
    loop = 0

    # bellman-ford
    updated = True
    while updated:
        updated = False
        for i in range(m):
            a, b, c = edges[i]
            if not valid[a]:
                continue
            if not valid[b]:
                continue

            new_cost = scores[a] + c
            if new_cost < scores[b]:
                updated = True
                scores[b] = new_cost

        loop += 1
        if loop > n:
            print(-1)
            return

    print(max(0, -scores[-1]))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc137/tasks/abc137_e

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n, m, p = map(int, input().split())
    edges = []
    graph = defaultdict(list)
    rev_graph = defaultdict(list)

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

    # pick up nodes on goal path
    reachable_from_start = [False] * n

    # print(edges)
    def dfs(node):
        if reachable_from_start[node]:
            return
        reachable_from_start[node] = True
        for next_node in graph[node]:
            dfs(next_node)

    reachable_to_end = [False] * n

    def rdfs(node):
        if reachable_to_end[node]:
            return
        reachable_to_end[node] = True
        for next_node in rev_graph[node]:
            rdfs(next_node)

    dfs(0)
    rdfs(n-1)

    valid = [False] * n
    for i in range(n):
        valid[i] = reachable_from_start[i] and reachable_to_end[i]

    inf = 10**10
    scores = [inf] * n
    scores[0] = 0
    loop = 0

    # bellman-ford
    updated = True
    while updated:
        updated = False
        for i in range(m):
            a, b, c = edges[i]
            if not valid[a]:
                continue
            if not valid[b]:
                continue

            new_cost = scores[a] + c
            if new_cost < scores[b]:
                updated = True
                scores[b] = new_cost

        loop += 1
        if loop > n:
            print(-1)
            return

    print(max(0, -scores[-1]))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc137/tasks/abc137_e

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n, m, p = map(int, input().split())
    edges = []
    graph = defaultdict(list)
    rev_graph = defaultdict(list)

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

    # pick up nodes on goal path
    reachable_from_start = [False] * n

    print(edges)
    def dfs(node):
        if reachable_from_start[node]:
            return
        reachable_from_start[node] = True
        for next_node in graph[node]:
            dfs(next_node)

    reachable_to_end = [False] * n

    def rdfs(node):
        if reachable_to_end[node]:
            return
        reachable_to_end[node] = True
        for next_node in rev_graph[node]:
            rdfs(next_node)

    dfs(0)
    # rdfs(n-1)

    valid = [False] * n
    for i in range(n):
        valid[i] = reachable_from_start[i] and reachable_to_end[i]

    inf = 10**10
    scores = [inf] * n
    scores[0] = 0
    loop = 0

    # bellman-ford
    updated = True
    while updated:
        updated = False
        for i in range(m):
            a, b, c = edges[i]
            if not valid[a]:
                continue
            if not valid[b]:
                continue

            new_cost = scores[a] + c
            if new_cost < scores[b]:
                updated = True
                scores[b] = new_cost

        loop += 1
        if loop > n:
            print(-1)
            return

    print(max(0, -scores[-1]))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc137/tasks/abc137_e

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n, m, p = map(int, input().split())
    edges = []
    graph = defaultdict(list)
    rev_graph = defaultdict(list)

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

    # pick up nodes on goal path
    reachable_from_start = [False] * 2501

    print(edges)
    def dfs(node):
        if reachable_from_start[node]:
            return
        reachable_from_start[node] = True
        for next_node in graph[node]:
            dfs(next_node)

    reachable_to_end = [False] * 2501

    def rdfs(node):
        if reachable_to_end[node]:
            return
        reachable_to_end[node] = True
        for next_node in rev_graph[node]:
            rdfs(next_node)

    dfs(0)
    rdfs(n-1)

    valid = [False] * 2501
    for i in range(n):
        valid[i] = reachable_from_start[i] and reachable_to_end[i]

    inf = 10**10
    scores = [inf] * n
    scores[0] = 0
    loop = 0

    # bellman-ford
    updated = True
    while updated:
        updated = False
        for i in range(m):
            a, b, c = edges[i]
            if not valid[a]:
                continue
            if not valid[b]:
                continue

            new_cost = scores[a] + c
            if new_cost < scores[b]:
                updated = True
                scores[b] = new_cost

        loop += 1
        if loop > n:
            print(-1)
            return

    print(max(0, -scores[-1]))


if __name__ == '__main__':
    main()
# https://atcoder.jp/contests/abc137/tasks/abc137_e

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n, m, p = map(int, input().split())
    edges = []
    graph = defaultdict(list)
    rev_graph = defaultdict(list)

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

    # pick up nodes on goal path
    reachable_from_start = [False] * 2501

    print(edges)
    def dfs(node):
        if reachable_from_start[node]:
            return
        reachable_from_start[node] = True
        for next_node in graph[node]:
            dfs(next_node)

    reachable_to_end = [False] * 2501

    def rdfs(node):
        if reachable_to_end[node]:
            return
        reachable_to_end[node] = True
        for next_node in rev_graph[node]:
            rdfs(next_node)

    dfs(0)
    rdfs(n-1)

    valid = [False] * 2501
    for i in range(n):
        valid[i] = reachable_from_start[i] and reachable_to_end[i]

    inf = 10**10
    scores = [inf] * n
    scores[0] = 0
    loop = 0

    # bellman-ford
    updated = True
    while updated:
        updated = False
        for i in range(m):
            a, b, c = edges[i]
            if not valid[a]:
                continue
            if not valid[b]:
                continue

            new_cost = scores[a] + c
            if new_cost < scores[b]:
                updated = True
                scores[b] = new_cost

        loop += 1
        if loop > n:
            print(-1)
            return

    print(max(0, -scores[-1]))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc137/tasks/abc137_e

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n, m, p = map(int, input().split())
    edges = []
    graph = defaultdict(list)
    rev_graph = defaultdict(list)

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

    # pick up nodes on goal path
    reachable_from_start = [False] * n

    def dfs(node):
        if reachable_from_start[node]:
            return
        reachable_from_start[node] = True
        for next in graph[node]:
            dfs(next)

    dfs(0)

    reachable_to_end = [False] * n

    def rdfs(node):
        if reachable_to_end[node]:
            return
        reachable_to_end[node] = True
        for next in rev_graph[node]:
            rdfs(next)

    rdfs(n-1)

    valid = [False] * n
    for i in range(n):
        valid[i] = reachable_from_start[i] and reachable_to_end[i]

    inf = 10**10
    scores = [inf] * n
    scores[0] = 0
    loop = 0
    #
    # # bellman-ford
    # updated = True
    # while updated:
    #     updated = False
    #     for i in range(m):
    #         a, b, c = edges[i]
    #         if not valid[a]:
    #             continue
    #         if not valid[b]:
    #             continue
    #
    #         new_cost = scores[a] + c
    #         if new_cost < scores[b]:
    #             updated = True
    #             scores[b] = new_cost
    #
    #     loop += 1
    #     if loop > n:
    #         print(-1)
    #         return

    print(max(0, -scores[-1]))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n, m, p = map(int, input().split())
    edges = []
    graph = defaultdict(list)
    rev_graph = defaultdict(list)

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

    # pick up nodes on goal path
    reachable_from_start = [False] * n

    def dfs(node):
        if reachable_from_start[node]:
            return
        reachable_from_start[node] = True
        for next in graph[node]:
            dfs(next)

    dfs(0)

    reachable_to_end = [False] * n

    def rdfs(node):
        if reachable_to_end[node]:
            return
        reachable_to_end[node] = True
        for next in rev_graph[node]:
            rdfs(next)

    rdfs(n-1)

    valid = [False] * n
    for i in range(n):
        valid[i] = reachable_from_start[i] and reachable_to_end[i]

    inf = 10**10
    scores = [inf] * n
    scores[0] = 0
    loop = 0

    # bellman-ford
    updated = True
    while updated:
        updated = False
        for i in range(m):
            a, b, c = edges[i]
            if not valid[a]:
                continue
            if not valid[b]:
                continue

            new_cost = scores[a] + c
            if new_cost < scores[b]:
                updated = True
                scores[b] = new_cost

        loop += 1
        if loop > n:
            print(-1)
            return

    print(max(0, -scores[-1]))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n, m, p = map(int, input().split())
    edges = []
    graph = defaultdict(list)
    rev_graph = defaultdict(list)

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

    # pick up nodes on goal path
    reachabel_from_start = [False] * n

    def dfs(node):
        if reachabel_from_start[node]:
            return
        reachabel_from_start[node] = True
        for next in graph[node]:
            dfs(next)

    dfs(0)

    reachabel_to_end = [False] * n

    def rdfs(node):
        if reachabel_to_end[node]:
            return
        reachabel_to_end[node] = True
        for next in rev_graph[node]:
            rdfs(next)

    rdfs(n-1)

    inf = 10**10
    scores = [inf] * n
    scores[0] = 0
    loop = 0
    # print(reachabelFromStart)
    # print(reachabelToEnd)
    # bellman-ford
    updated = True
    while updated:
        updated = False
        for i in range(m):
            a, b, c = edges[i]
            if reachabel_from_start[a] and reachabel_to_end[a] and reachabel_from_start[b] and reachabel_to_end[b]:
                new_cost = scores[a] + c
                if new_cost < scores[b]:
                    updated = True
                    scores[b] = new_cost
        loop += 1
        if loop > n:
            print(-1)
            return

    print(max(0, -scores[-1]))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n, m, p = map(int, input().split())
    edges = []
    graph = defaultdict(list)
    rev_graph = defaultdict(list)
    coins = {}
    for _ in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        c = -(c-p)
        edges.append((a,b,c))
        graph[a].append(b)
        rev_graph[b].append(a)

    # pick up nodes on goal path
    reachabelFromStart = [False] * n

    def dfs(node):
        if reachabelFromStart[node]:
            return
        reachabelFromStart[node] = True
        for next in graph[node]:
            dfs(next)

    dfs(0)

    reachabelToEnd = [False] * n
    def rdfs(node):
        if reachabelToEnd[node]:
            return
        reachabelToEnd[node] = True
        for next in rev_graph[node]:
            rdfs(next)

    rdfs(n-1)

    inf = 10**10
    scores = [inf] * n
    scores[0] = 0
    loop = 0
    # print(reachabelFromStart)
    # print(reachabelToEnd)
    # bellman-ford
    while True:
        updated = False
        for i in range(m):
            a, b, c = edges[i]
            if reachabelFromStart[a] and reachabelToEnd[a] and reachabelFromStart[b] and reachabelToEnd[b]:
                new_cost = scores[a] + c
                if new_cost < scores[b]:
                    updated = True
                    scores[b] = new_cost
        loop += 1
        if loop > n:
            if updated:
                print(-1)
                break
            else:
                print(max(0,-scores[-1]))
                break


if __name__ == '__main__':
    main()