- 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
- 83 lines of Python from the credited upstream file abc021_c.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 visited = [False for _ in range(vertex_count)]25 path_count = [0 for _ in range(vertex_count)]26 path_count[source] = 127 mod = 10 ** 9 + 728 29 while hq:30 cost, vertex = heappop(hq)31 32 if cost > costs[vertex]:33 continue34 35 if visited[vertex]:36 continue37 38 visited[vertex] = True39 40 for weight, edge in edges[vertex]:41 new_cost = cost + weight42 43 if new_cost <= costs[edge]:44 costs[edge] = new_cost45 46 path_count[edge] += path_count[vertex]47 path_count[edge] %= mod48 49 heappush(hq, (new_cost, edge))50 51 return path_count52 53 54def main():55 import sys56 57 input = sys.stdin.readline58 59 n = int(input())60 a, b = map(int, input().split())61 a -= 162 b -= 163 m = int(input())64 edges = [[] for _ in range(n)]65 66 for _ in range(m):67 xi, yi = map(int, input().split())68 xi -= 169 yi -= 170 71 72 73 edges[xi].append((1, yi))74 edges[yi].append((1, xi))75 76 path_counts = dijkstra(vertex_count=n, source=a, edges=edges)77 78 print(path_counts[b])79 80 81if __name__ == "__main__":82 main()83