堆优化 Dijkstra

一句话理解

堆优化 Dijkstra：每次取 dist 最小的未确定点。

为什么要学

正权图最短路。

讲解

小根堆存 {dist,u}。松弛时 push 新值，旧值懒惰丢弃。O((n+m) log n)。

例子

和普通 Dijkstra 选点从 O(n) 变 O(log n)。

常见错误

• 负权。
• 出堆不判断 d>dist[u]。