- 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 abc305_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, edges, ph):5 from heapq import heappop, heappush6 7 hq = [] 8 pending = -19 dists = [pending for _ in range(vertex_count)]10 11 for pi, hi in ph:12 pi -= 113 hq.append((-hi, pi))14 dists[pi] = hi15 16 while hq:17 dist, vertex = heappop(hq)18 dist *= -119 20 if dist != dists[vertex]:21 continue22 23 for edge in edges[vertex]:24 new_dist = dist - 125 26 if dists[edge] >= new_dist:27 continue28 29 dists[edge] = new_dist30 heappush(hq, (-new_dist, edge))31 32 return dists33 34 35def main():36 import sys37 38 input = sys.stdin.readline39 40 n, m, k = map(int, input().split())41 graph = [[] for _ in range(n)]42 43 for _ in range(m):44 ai, bi = map(int, input().split())45 ai -= 146 bi -= 147 48 graph[ai].append(bi)49 graph[bi].append(ai)50 51 ph = [tuple(map(int, input().split())) for _ in range(k)]52 dist = dijkstra(vertex_count=n, edges=graph, ph=ph)53 54 ans = [i for i, di in enumerate(dist, 1) if di >= 0]55 56 print(len(ans))57 print(*ans)58 59 60if __name__ == "__main__":61 main()62