Approach
Breadth-first search
For ABC292 E — Transitivity, 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
- 63 lines of Python from the credited upstream file abc292_e.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 4from collections import deque5 6 7def bfs(vertex_count, source, graph):8 inf = float("inf")9 costs = [inf for _ in range(vertex_count)]10 costs[source] = 011 visited = [False for _ in range(vertex_count)]12 q = deque([source])13 14 while q:15 cur = q.popleft()16 17 if visited[cur]:18 continue19 20 visited[cur] = True21 22 for to in graph[cur]:23 if visited[to]:24 continue25 26 costs[to] = min(costs[to], costs[cur] + 1)27 q.append(to)28 29 return costs30 31 32def main():33 import sys34 35 input = sys.stdin.readline36 37 n, m = map(int, input().split())38 edges = [[] for _ in range(n)]39 40 for _ in range(m):41 ai, bi = map(int, input().split())42 ai -= 143 bi -= 144 edges[ai].append(bi)45 46 inf = float('inf')47 ans = 048 49 for i in range(n):50 dist = bfs(n, i, edges)51 52 for di in dist:53 if di == 0 or di == 1 or di == inf:54 continue55 56 ans += 157 58 print(ans)59 60 61if __name__ == "__main__":62 main()63