- 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
- 72 lines of Python from the credited upstream file abc012_4.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 pending = -125 parents = [pending for _ in range(vertex_count)]26 27 while hq:28 cost, vertex = heappop(hq)29 30 if cost > costs[vertex]:31 continue32 33 for weight, edge in edges[vertex]:34 new_cost = cost + weight35 36 if new_cost < costs[edge]:37 costs[edge] = new_cost38 parents[edge] = vertex39 heappush(hq, (new_cost, edge))40 41 return costs, parents42 43 44def main():45 import sys46 47 input = sys.stdin.readline48 49 n, m = map(int, input().split())50 inf = float("inf")51 graph = [[] for _ in range(n)]52 53 for _ in range(m):54 ai, bi, ti = map(int, input().split())55 ai -= 156 bi -= 157 58 graph[ai].append((ti, bi))59 graph[bi].append((ti, ai))60 61 ans = inf62 63 for i in range(n):64 costs, _ = dijkstra(n, i, graph)65 ans = min(ans, max(costs))66 67 print(ans)68 69 70if __name__ == "__main__":71 main()72