Approach
Breadth-first search
For ABC454 C — Straw Millionaire, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 55 lines of Python from the credited upstream file abc454_c.py.
- The implementation visibly relies on sequence storage, ordered lookup, work queue.
- No explicit loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
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 main():5 import sys6 from collections import deque7 from typing import Any, List, Tuple8 9 input = sys.stdin.readline10 11 n, m = map(int, input().split())12 inf = 10**1813 graph = [[] for _ in range(n)]14 15 for _ in range(m):16 ai, bi = map(int, input().split())17 ai -= 118 bi -= 119 20 graph[ai].append(bi)21 22 def bfs_for_graph(23 vertex_count: int, graph: List[List[int]], start_id: int24 ) -> Tuple[List[bool], List[int]]:25 d = deque([start_id])26 visited = [False] * vertex_count27 dist = [inf] * vertex_count28 dist[start_id] = 029 30 while d:31 cur = d.popleft()32 33 if visited[cur]:34 continue35 36 visited[cur] = True37 38 for to in graph[cur]:39 if visited[to]:40 continue41 42 d.append(to)43 dist[to] = min(dist[to], dist[cur] + 1)44 45 return visited, dist46 47 start_id = 048 visited, dist = bfs_for_graph(vertex_count=n, graph=graph, start_id=start_id)49 ans = sum([1 for v in visited if v])50 print(ans)51 52 53if __name__ == "__main__":54 main()55