Problem p03722 (python)

Fixed submission:
import sys
sys.setrecursionlimit(100000)

def set_enable_goal(cur_node, back_paths, enable_goal):
    if cur_node in back_paths:
        for next_node in back_paths[cur_node]:
            if enable_goal[next_node - 1] == 0:
                enable_goal[next_node - 1] = 1
                set_enable_goal(next_node, back_paths, enable_goal)


N, M = map(int, input().split())
MIN = float('-inf')
INF_LIMIT = -MIN

back_paths = {}
all_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if a in all_paths:
        all_paths[a].append((b, c))
    else:
        all_paths[a] = [(b, c)]

    if b in back_paths:
        back_paths[b].append(a)
    else:
        back_paths[b] = [a]


# path cut
enable_goal= [0 for i in range(N)]
enable_goal[N - 1] = 1
set_enable_goal(N, back_paths, enable_goal)

for a, paths in all_paths.items():
    if not enable_goal[a - 1]:
        all_paths[a] = []
    else:
        valid_paths = []
        for b, c in paths:
            if enable_goal[b - 1]:
                valid_paths.append((b, c))
        all_paths[a] = valid_paths


scores = [MIN for i in range(N)]
scores[0] = 0

is_inf = False
for n in range(N):
    for a in all_paths.keys():
        for b, c in all_paths[a]:
            scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)

# loop check
if not is_inf:
    prev_score = scores[N - 1]
    for a in all_paths.keys():
        for b, c in all_paths[a]:
            scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)
    if prev_score != scores[N - 1]:
        is_inf = True


if is_inf:
    print('inf')
else:
    print(scores[N - 1])

Buggy submission (verdict: Runtime Error):
import sys

def set_enable_goal(cur_node, back_paths, enable_goal):
    if cur_node in back_paths:
        for next_node in back_paths[cur_node]:
            if enable_goal[next_node - 1] == 0:
                enable_goal[next_node - 1] = 1
                set_enable_goal(next_node, back_paths, enable_goal)


N, M = map(int, input().split())
MIN = float('-inf')
INF_LIMIT = 20000000000

back_paths = {}
all_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if b in back_paths:
        back_paths[b].append(a)
    else:
        back_paths[b] = [a]

    if a in all_paths:
        all_paths[a].append((b, c))
    else:
        all_paths[a] = [(b, c)]

enable_goal= [0 for i in range(N)]
enable_goal[N - 1] = 1
set_enable_goal(N, back_paths, enable_goal)

for a, paths in all_paths.items():
    if not enable_goal[a - 1]:
        all_paths[a] = []
    else:
        valid_paths = []
        for b, c in paths:
            if enable_goal[b - 1]:
                valid_paths.append((b, c))
        all_paths[a] = valid_paths


scores = [MIN for i in range(N)]
scores[0] = 0

is_inf = False
for n in range(N):
    for a in range(1, M + 1):
        if a in all_paths:
            for b, c in all_paths[a]:
                if scores[a - 1] + c > INF_LIMIT or scores[a - 1] + c < -INF_LIMIT:
                    is_inf = True
                    break
                else:
                    scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)

# loop check
if not is_inf:
    prev_scores = list(scores)
    for a in range(1, M + 1):
        if a in all_paths:
            for b, c in all_paths[a]:
                scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)
    for p, s in zip(prev_scores, scores):
        if p != s:
            is_inf = True
            break

if is_inf:
    print('inf')
else:
    print(scores[N - 1])

Buggy submission (verdict: Runtime Error):
import sys

def set_enable_goal(cur_node, back_paths, enable_goal):
    if cur_node in back_paths:
        for next_node in back_paths[cur_node]:
            if enable_goal[next_node - 1] == 0:
                enable_goal[next_node - 1] = 1
                set_enable_goal(next_node, back_paths, enable_goal)


N, M = map(int, input().split())
MIN = float('-inf')

back_paths = {}
all_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if b in back_paths:
        back_paths[b].append(a)
    else:
        back_paths[b] = [a]

    if a in all_paths:
        all_paths[a].append((b, c))
    else:
        all_paths[a] = [(b, c)]

enable_goal= [0 for i in range(N)]
enable_goal[N - 1] = 1
set_enable_goal(N, back_paths, enable_goal)

for a, paths in all_paths.items():
    if not enable_goal[a - 1]:
        all_paths[a] = []
    else:
        valid_paths = []
        for b, c in paths:
            if enable_goal[b - 1]:
                valid_paths.append((b, c))
        all_paths[a] = valid_paths


scores = [MIN for i in range(N)]
scores[0] = 0

is_inf = False
for n in range(N):
    for a in range(1, M + 1):
        if a in all_paths:
            for b, c in all_paths[a]:
                scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)

# loop check
if not is_inf:
    prev_scores = list(scores)
    for a in range(1, M + 1):
        if a in all_paths:
            for b, c in all_paths[a]:
                scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)
    for p, s in zip(prev_scores, scores):
        if p != s:
            is_inf = True
            break

if is_inf:
    print('inf')
else:
    print(scores[N - 1])

Buggy submission (verdict: Runtime Error):
def trans(cur, prev_paths, score, goal_score, paths, N):
    # inf check
    if cur in prev_paths:
        return 'inf'
    if cur == N:
        goal_score = score
    if not cur in paths:
        return goal_score

    nodes = paths[cur]
    score_updated = False
    for n, s in nodes:
        new_score = score + s
        new_prev_paths = dict(prev_paths)
        new_prev_paths[cur] = 1
        tmp_goal_score = trans(n, new_prev_paths, new_score, goal_score, paths, N)
        if tmp_goal_score == 'inf':
            return 'inf'
        elif not score_updated or tmp_goal_score > goal_score:
            goal_score = tmp_goal_score
            score_updated = True

    return goal_score


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

paths = {}
prev_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if a in paths:
        paths[a].append((b, c))
    else:
        paths[a] = [(b, c)] 

cur_node = 1
prev_node = -1
score = trans(cur_node, prev_paths, 0, 0, paths, N)
print(score)

Buggy submission (verdict: Runtime Error):
def trans(cur, prev_paths, score, goal_score, paths, N):
    # inf check
    if cur in prev_paths:
        return 'inf'
    if cur == N:
        goal_score = score
    if not cur in paths:
        return goal_score

    nodes = paths[cur]
    for n, s in nodes:
        new_score = score + s
        new_prev_paths = dict(prev_paths)
        new_prev_paths[cur] = 1
        tmp_goal_score = trans(n, new_prev_paths, new_score, goal_score, paths, N)
        if tmp_goal_score == 'inf':
            return 'inf'
        elif tmp_goal_score > goal_score:
            goal_score = tmp_goal_score

    return goal_score


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

paths = {}
prev_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if a in paths:
        paths[a].append((b, c))
    else:
        paths[a] = [(b, c)] 

cur_node = 1
prev_node = -1
score = trans(cur_node, prev_paths, 0, 0, paths, N)
print(score)

Buggy submission (verdict: Runtime Error):
def trans(cur, prev, score, paths, N):
    # inf check
    if cur in prev_paths:
        return 'inf'
    if cur == N and not cur in paths:
        return score

    nodes = paths[cur]
    for n, s in nodes:
        score += s
        prev_paths[cur] = 1
        return trans(n, prev_paths, score, paths, N)


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

paths = {}
prev_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if a in paths:
        paths[a].append((b, c))
    else:
        paths[a] = [(b, c)] 

cur_node = 1
prev_node = -1
score = trans(cur_node, prev_paths, 0, paths, N)
print(score)

Buggy submission (verdict: Runtime Error):
def trans(cur, prev, score, paths, N):
    # inf check
    if cur in paths:
        nodes = paths[cur]
        for n, s in nodes:
            if prev == n:
                return 'inf'
    if cur == N:
        return score

    nodes = paths[cur]
    for n, s in nodes:
        score += s
        return trans(n, cur, score, paths, N)


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

paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if a in paths:
        paths[a].append((b, c))
    else:
        paths[a] = [(b, c)] 

cur_node = 1
prev_node = -1
score = trans(cur_node, prev_node, 0, paths, N)
print(score)