- 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
- 71 lines of Python from the credited upstream file abc309_d.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 from heapq import heappop, heappush6 7 hq = [(0, source)] 8 inf = 10**189 costs = [inf for _ in range(vertex_count)]10 costs[source] = 011 visited = [False for _ in range(vertex_count)]12 pending = -113 parents = [pending for _ in range(vertex_count)]14 15 while hq:16 cost, vertex = heappop(hq)17 18 if cost > costs[vertex]:19 continue20 21 if visited[vertex]:22 continue23 24 visited[vertex] = True25 26 for weight, edge in edges[vertex]:27 new_cost = cost + weight28 29 if new_cost < costs[edge]:30 costs[edge] = new_cost31 parents[edge] = vertex32 heappush(hq, (new_cost, edge))33 34 return costs, parents35 36 37def main():38 import sys39 40 input = sys.stdin.readline41 42 n1, n2, m = map(int, input().split())43 edges1 = [[] for _ in range(n1)]44 edges2 = [[] for _ in range(n2)]45 46 for _ in range(m):47 ai, bi = map(int, input().split())48 ai -= 149 bi -= 150 51 52 ci = 153 54 if ai < n1:55 edges1[ai].append((ci, bi))56 edges1[bi].append((ci, ai))57 else:58 ai -= n159 bi -= n160 edges2[ai].append((ci, bi))61 edges2[bi].append((ci, ai))62 63 dist1, _ = dijkstra(vertex_count=n1, source=0, edges=edges1)64 dist2, _ = dijkstra(vertex_count=n2, source=n2 - 1, edges=edges2)65 66 print(max(dist1) + max(dist2) + 1)67 68 69if __name__ == "__main__":70 main()71