- 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 abc342_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 from heapq import heappop, heappush7 8 input = sys.stdin.readline9 10 n, m = map(int, input().split())11 edges = [[] for _ in range(n)]12 13 for _ in range(m):14 li, di, ki, ci, to, bi = map(int, input().split())15 to -= 116 bi -= 117 18 19 edges[bi].append((to, li, di, ki, ci))20 21 inf = 10**1922 hq = [(-inf, n - 1)] 23 ts = [-inf] * n24 ts[-1] = inf25 26 while hq:27 ti, vertex = heappop(hq)28 ti = -ti29 30 if ti != ts[vertex]:31 continue32 33 for to, li, di, ki, ci in edges[vertex]:34 nt = ti - ci35 36 if li > nt:37 continue38 39 k_candidate = (nt - li) di40 k_candidate = min(k_candidate, ki - 1)41 new_cost = li + k_candidate * di42 43 if new_cost <= ts[to]:44 continue45 46 ts[to] = new_cost47 heappush(hq, (-new_cost, to))48 49 for ti in ts[:-1]:50 if ti == -inf:51 ti = "Unreachable"52 53 print(ti)54 55 56if __name__ == "__main__":57 main()58