- 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
- 78 lines of Python from the credited upstream file abc362_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 main():5 import sys6 7 input = sys.stdin.readline8 9 n, m = map(int, input().split())10 a = list(map(int, input().split()))11 edges = [[] for _ in range(n)]12 13 for _ in range(m):14 ui, vi, bi = map(int, input().split())15 ui -= 116 vi -= 117 18 19 20 edges[ui].append((bi, vi))21 edges[vi].append((bi, ui))22 23 def dijkstra(vertex_count: int, source: int, edges):24 """Uses Dijkstra's algorithm to find the shortest path in a graph.25 26 Args:27 vertex_count: The number of vertices.28 source : Vertex number (0-indexed).29 edges : List of (cost, edge) (0-indexed).30 31 Returns:32 costs : List of the shortest distance.33 parents: List of parent vertices.34 35 Landau notation: O(|Edges|log|Vertices|).36 37 See:38 https:atcoder.jp/contests/abc191/submissions/1996407839 https:atcoder.jp/contests/abc191/submissions/1996623240 """41 42 from heapq import heappop, heappush43 44 hq = [(a[0], source)] 45 costs = [float("inf") for _ in range(vertex_count)]46 costs[source] = a[0]47 visited = [False for _ in range(vertex_count)]48 pending = -149 parents = [pending for _ in range(vertex_count)]50 51 while hq:52 cost, vertex = heappop(hq)53 54 if cost > costs[vertex]:55 continue56 57 if visited[vertex]:58 continue59 60 visited[vertex] = True61 62 for weight, edge in edges[vertex]:63 new_cost = cost + weight + a[edge]64 65 if new_cost < costs[edge]:66 costs[edge] = new_cost67 parents[edge] = vertex68 heappush(hq, (new_cost, edge))69 70 return costs, parents71 72 dist, _ = dijkstra(vertex_count=n, source=0, edges=edges)73 print(*dist[1:])74 75 76if __name__ == "__main__":77 main()78