- 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
- 79 lines of Python from the credited upstream file abc252_e.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 11 Returns:12 costs : List of the shortest distance.13 parents: List of parent vertices.14 15 Landau notation: O(|Edges|log|Vertices|).16 17 See:18 https:atcoder.jp/contests/abc191/submissions/1996407819 https:atcoder.jp/contests/abc191/submissions/1996623220 """21 22 from heapq import heappop, heappush23 24 hq = [(0, source)] 25 costs = [float("inf") for _ in range(vertex_count)]26 costs[source] = 027 visited = [False for _ in range(vertex_count)]28 pending = -129 parents = [pending for _ in range(vertex_count)]30 road_ids = [-1] * len(edges)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, i 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 road_ids[edge] = i52 53 return road_ids54 55 56def main():57 import sys58 59 input = sys.stdin.readline60 61 n, m = map(int, input().split())62 edges = [[] for _ in range(n)]63 64 for i in range(m):65 ai, bi, ci = map(int, input().split())66 ai -= 167 bi -= 168 69 70 71 edges[ai].append((ci, bi, i + 1))72 edges[bi].append((ci, ai, i + 1))73 74 ans = dijkstra(vertex_count=n, source=0, edges=edges)75 print(*ans[1:])76 77if __name__ == "__main__":78 main()79