Approach
Breadth-first search
For ABC277 E — Crystal Switches, 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
- 98 lines of Python from the credited upstream file abc277_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 4def main():5 import sys6 7 input = sys.stdin.readline8 9 n, m, k = map(int, input().split())10 edges = [[] for _ in range(2 * n)]11 12 for _ in range(m):13 ai, bi, ci = map(int, input().split())14 ai -= 115 bi -= 116 17 18 19 if ci == 0:20 edges[ai + n].append((1, bi + n))21 edges[bi + n].append((1, ai + n))22 else:23 edges[ai].append((1, bi))24 edges[bi].append((1, ai))25 26 s = list(map(int, input().split()))27 28 for si in s:29 si -= 130 31 edges[si].append((0, si + n))32 edges[si + n].append((0, si))33 34 def dijkstra(vertex_count: int, source: int, edges):35 """Uses Dijkstra's algorithm to find the shortest path in a graph.36 37 Args:38 vertex_count: The number of vertices.39 source : Vertex number (0-indexed).40 edges : List of (cost, edge) (0-indexed).41 42 Returns:43 costs : List of the shortest distance.44 parents: List of parent vertices.45 46 Landau notation: O(|Edges|log|Vertices|).47 48 See:49 https:atcoder.jp/contests/abc191/submissions/1996407850 https:atcoder.jp/contests/abc191/submissions/1996623251 """52 53 from collections import deque54 55 d = deque([(0, source)])56 costs = [float("inf") for _ in range(vertex_count)]57 costs[source] = 058 visited = [False for _ in range(vertex_count)]59 pending = -160 parents = [pending for _ in range(vertex_count)]61 62 while d:63 cost, vertex = d.popleft()64 65 if cost > costs[vertex]:66 continue67 68 if visited[vertex]:69 continue70 71 visited[vertex] = True72 73 for weight, edge in edges[vertex]:74 new_cost = cost + weight75 76 if new_cost < costs[edge]:77 costs[edge] = new_cost78 parents[edge] = vertex79 80 if weight == 0:81 d.appendleft((new_cost, edge))82 else:83 d.append((new_cost, edge))84 85 return costs, parents86 87 dist, _ = dijkstra(vertex_count=2 * n, source=0, edges=edges)88 ans = min(dist[n - 1], dist[2 * n - 1])89 90 if ans == float('inf'):91 ans = -192 93 print(ans)94 95 96if __name__ == "__main__":97 main()98