Approach
Depth-first search
For ABC137 E — Coins Respawn, the implementation follows one branch at a time, making it suitable for components, trees, backtracking, or dependency exploration.
- Define the state carried into one recursive or stack frame.
- Mark or choose the current state before exploring children.
- Combine child results or undo the choice when the branch finishes.
Code notes
- 108 lines of Python from the credited upstream file abc137_e.py.
- The implementation visibly relies on sequence storage, ordered lookup.
- No explicit loop blocks detected.
Complexity
Count unique states for graph traversal; for backtracking, count the branching factor and maximum depth.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4def bellman_ford(5 vertex_count: int,6 edges,7 reachables=None,8 dist_max: int = 10 ** 18,9 start: int = 010):11 dist = [dist_max] * vertex_count12 dist[start] = 013 14 if reachables is None:15 reachables = [True] * vertex_count16 17 is_updated = True18 step_count = 019 has_cycle = False20 21 while is_updated:22 is_updated = False23 24 for ci, ai, bi in edges:25 if not reachables[ai] or not reachables[bi]:26 continue27 28 new_cost = dist[ai] + ci29 30 if new_cost < dist[bi]:31 dist[bi] = new_cost32 is_updated = True33 34 step_count += 135 36 if step_count > vertex_count:37 has_cycle = True38 break39 40 return has_cycle, dist41 42 43def main():44 import sys45 46 sys.setrecursionlimit(10 ** 7)47 input = sys.stdin.readline48 49 n, m, p = map(int, input().split())50 graph1 = [[] for _ in range(n)]51 graph2 = [[] for _ in range(n)]52 edges = list()53 54 for i in range(m):55 ai, bi, ci = map(int, input().split())56 ai -= 157 bi -= 158 ci -= p 59 ci *= -1 60 61 graph1[ai].append(bi)62 graph2[bi].append(ai)63 edges.append((ci, ai, bi))64 65 66 reachable_from_1 = [False] * n67 reachable_from_n = [False] * n68 69 def dfs1(v):70 if reachable_from_1[v]:71 return72 73 reachable_from_1[v] = True74 75 for to in graph1[v]:76 dfs1(to)77 78 def dfs2(v):79 if reachable_from_n[v]:80 return81 82 reachable_from_n[v] = True83 84 for to in graph2[v]:85 dfs2(to)86 87 dfs1(0)88 dfs2(n - 1)89 90 reachables = [False] * n91 92 for i, (case1, case2) in enumerate(zip(reachable_from_1, reachable_from_n)):93 if case1 and case2:94 reachables[i] = True95 96 97 has_cycle, dist = bellman_ford(n, edges, reachables)98 99 if has_cycle:100 print(-1)101 else:102 ans = max(0, -dist[n - 1]) 103 print(ans)104 105 106if __name__ == "__main__":107 main()108