- 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
- 62 lines of Python from the credited upstream file abc191_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 from heapq import heappop, heappush6 7 hq = [(0, source)] 8 costs = [float("inf") for _ in range(vertex_count)]9 costs[source] = 010 pending = -111 parents = [pending for _ in range(vertex_count)]12 13 while hq:14 cost, vertex = heappop(hq)15 16 if cost > costs[vertex]:17 continue18 19 for weight, edge in edges[vertex]:20 new_cost = cost + weight21 22 if new_cost < costs[edge]:23 costs[edge] = new_cost24 parents[edge] = vertex25 heappush(hq, (new_cost, edge))26 27 return costs, parents28 29 30def main():31 import sys32 33 input = sys.stdin.readline34 35 n, m = map(int, input().split())36 edges = [[] for _ in range(n)]37 reversed_edges = [[] for _ in range(n)]38 39 for _ in range(m):40 ai, bi, ci = map(int, input().split())41 ai -= 142 bi -= 143 44 edges[ai].append((ci, bi))45 reversed_edges[bi].append((ci, ai))46 47 for i in range(n):48 dist, _ = dijkstra(vertex_count=n, source=i, edges=edges)49 ans = float("inf")50 51 for cost, reversed_edge in reversed_edges[i]:52 ans = min(ans, dist[reversed_edge] + cost)53 54 if ans == float("inf"):55 print(-1)56 else:57 print(ans)58 59 60if __name__ == "__main__":61 main()62