- 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
- 75 lines of Python from the credited upstream file abc340_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 """Uses Dijkstra's algorithm to find the shortest path in a graph.6 7 Args:8 vertex_count: The number of vertices.9 source : Vertex number (0-indexed).10 edges : List of (cost, edge) (0-indexed).11 12 Returns:13 costs : List of the shortest distance.14 parents: List of parent vertices.15 16 Landau notation: O(|Edges|log|Vertices|).17 18 See:19 https:atcoder.jp/contests/abc191/submissions/1996407820 https:atcoder.jp/contests/abc191/submissions/1996623221 """22 23 from heapq import heappop, heappush24 25 hq = [(0, source)] 26 costs = [float("inf") for _ in range(vertex_count)]27 costs[source] = 028 visited = [False for _ in range(vertex_count)]29 pending = -130 parents = [pending for _ in range(vertex_count)]31 32 while hq:33 cost, vertex = heappop(hq)34 35 if cost > costs[vertex]:36 continue37 38 if visited[vertex]:39 continue40 41 visited[vertex] = True42 43 for weight, edge in edges[vertex]:44 new_cost = cost + weight45 46 if new_cost < costs[edge]:47 costs[edge] = new_cost48 parents[edge] = vertex49 heappush(hq, (new_cost, edge))50 51 return costs, parents52 53 54def main():55 import sys56 57 input = sys.stdin.readline58 59 n = int(input())60 edges = [[] for _ in range(n)]61 62 for i in range(n - 1):63 ai, bi, xi = map(int, input().split())64 xi -= 165 66 edges[i].append((ai, i + 1))67 edges[i].append((bi, xi))68 69 dist, _ = dijkstra(vertex_count=n, source=0, edges=edges)70 print(dist[-1])71 72 73if __name__ == "__main__":74 main()75