- 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
- 58 lines of Python from the credited upstream file abc192_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, dep_time in edges[vertex]:20 new_cost = cost + ((dep_time - cost) % dep_time) + weight21 22 if new_cost < costs[edge]:23 costs[edge] = new_cost24 parents[edge] = vertex25 heappush(hq, (new_cost, edge))26 27 return costs28 29 30def main():31 import sys32 33 input = sys.stdin.readline34 35 n, m, x, y = map(int, input().split())36 edges = [[] for _ in range(n)]37 x -= 138 y -= 139 40 for _ in range(m):41 ai, bi, ti, ki = map(int, input().split())42 ai -= 143 bi -= 144 edges[ai].append((ti, bi, ki))45 edges[bi].append((ti, ai, ki))46 47 dist = dijkstra(vertex_count=n, source=x, edges=edges)48 ans = dist[y]49 50 if ans == float("inf"):51 ans = -152 53 print(ans)54 55 56if __name__ == "__main__":57 main()58