- Define the priority key and whether the smallest or largest item should lead.
- Push each candidate when it becomes eligible.
- Discard stale entries when necessary and process the best live candidate.
Code notes
- 85 lines of Python from the credited upstream file arc109_a.py.
- The implementation visibly relies on sequence storage, ordered lookup, work queue.
- No explicit loop blocks detected.
Complexity
Count heap pushes and pops; each normally contributes a logarithmic factor in the heap size.
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 dijkstra(vertex_count: int, source: int, edges):5 """Uses Dijkstra's algorithm to find the shortest path in a graph.6 Args:7 vertex_count: The number of vertices.8 source : Vertex number (0-indexed).9 edges : List of (cost, edge) (0-indexed).10 Returns:11 costs : List of the shortest distance.12 parents: List of parent vertices.13 Landau notation: O(|Edges|log|Vertices|).14 See:15 https:atcoder.jp/contests/abc191/submissions/1996407816 https:atcoder.jp/contests/abc191/submissions/1996623217 """18 19 from heapq import heappop, heappush20 21 hq = [(0, source)] 22 costs = [float("inf") for _ in range(vertex_count)]23 costs[source] = 024 visited = [False for _ in range(vertex_count)]25 pending = -126 parents = [pending for _ in range(vertex_count)]27 28 while hq:29 cost, vertex = heappop(hq)30 31 if cost > costs[vertex]:32 continue33 34 if visited[vertex]:35 continue36 37 visited[vertex] = True38 39 for weight, edge in edges[vertex]:40 new_cost = cost + weight41 42 if new_cost < costs[edge]:43 costs[edge] = new_cost44 parents[edge] = vertex45 heappush(hq, (new_cost, edge))46 47 return costs, parents48 49 50def main():51 import sys52 53 input = sys.stdin.readline54 55 a, b, x, y = map(int, input().split())56 a -= 157 b -= 158 b += 10059 60 edges = [[] for _ in range(201)]61 62 for i in range(100):63 64 65 edges[i + 100].append((x, i))66 edges[i].append((x, i + 100))67 68 if i >= 1:69 edges[i + 99].append((x, i))70 edges[i].append((x, i + 99))71 72 if i < 99:73 edges[i].append((y, i + 1))74 edges[i + 1].append((y, i))75 76 edges[i + 100].append((y, i + 101))77 edges[i + 101].append((y, i + 100))78 79 dist, _ = dijkstra(vertex_count=200, source=a, edges=edges)80 print(dist[b])81 82 83if __name__ == "__main__":84 main()85