Approach
Heap or priority queue
For ABC325 E — Our clients, please wait a moment, the implementation repeatedly takes the currently best candidate from a heap while inserting newly available choices.
- 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
- 112 lines of Python from the credited upstream file abc325_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 main():5 import sys6 7 input = sys.stdin.readline8 9 n, a, b, c = map(int, input().split())10 d = [list(map(int, input().split())) for _ in range(n)]11 edges = [[] for _ in range(n)]12 13 for i in range(n):14 for j in range(n):15 ci = d[i][j]16 edges[i].append((ci, j))17 18 def dijkstra(vertex_count: int, source: int, edges):19 """Uses Dijkstra's algorithm to find the shortest path in a graph.20 21 Args:22 vertex_count: The number of vertices.23 source : Vertex number (0-indexed).24 edges : List of (cost, edge) (0-indexed).25 26 Returns:27 costs : List of the shortest distance.28 parents: List of parent vertices.29 30 Landau notation: O(|Edges|log|Vertices|).31 32 See:33 https:atcoder.jp/contests/abc191/submissions/1996407834 https:atcoder.jp/contests/abc191/submissions/1996623235 """36 37 from heapq import heappop, heappush38 39 hq = [(0, source)] 40 costs = [float("inf") for _ in range(vertex_count)]41 costs[source] = 042 visited = [False for _ in range(vertex_count)]43 pending = -144 parents = [pending for _ in range(vertex_count)]45 46 while hq:47 cost, vertex = heappop(hq)48 49 if cost > costs[vertex]:50 continue51 52 if visited[vertex]:53 continue54 55 visited[vertex] = True56 57 for weight, edge in edges[vertex]:58 new_cost = cost + weight * a59 60 if new_cost < costs[edge]:61 costs[edge] = new_cost62 parents[edge] = vertex63 heappush(hq, (new_cost, edge))64 65 return costs, parents66 67 def dijkstra2(vertex_count: int, source: int, edges):68 from heapq import heappop, heappush69 70 hq = [(0, source)] 71 costs = [float("inf") for _ in range(vertex_count)]72 costs[source] = 073 visited = [False for _ in range(vertex_count)]74 pending = -175 parents = [pending for _ in range(vertex_count)]76 77 while hq:78 cost, vertex = heappop(hq)79 80 if cost > costs[vertex]:81 continue82 83 if visited[vertex]:84 continue85 86 visited[vertex] = True87 88 for weight, edge in edges[vertex]:89 new_cost = cost + weight * b + c90 91 if new_cost < costs[edge]:92 costs[edge] = new_cost93 parents[edge] = vertex94 heappush(hq, (new_cost, edge))95 96 return costs, parents97 98 dist, _ = dijkstra(vertex_count=n, source=0, edges=edges)99 dist2, _ = dijkstra2(vertex_count=n, source=n - 1, edges=edges)100 101 102 ans = float("inf")103 104 for d1, d2 in zip(dist, dist2):105 ans = min(ans, d1 + d2)106 107 print(ans)108 109 110if __name__ == "__main__":111 main()112