std::priority_queue 默认不能更新节点权重，因其基于堆实现、不支持随机访问或修改中间元素，只能重新插入新条目并配合懒删除机制处理重复节点。
为什么 std::priority_queue 默认不能更新节点权重？
因为 std::priority_queue 是基于堆的容器适配器，不支持随机访问或修改中间元素。一旦某个节点（比如顶点 v）被插入队列，后续即使你发现到它的更短距离，也无法在队列中“找到并更新”它——只能重新插入一个新条目 (new_dist, v)。这会导致队列中存在多个相同顶点、不同距离的副本。
实际编码中必须接受这个事实：靠“懒删除”处理重复节点。即每次 pop() 时检查当前取出的距离是否等于 dist[v] 的最新值，不等就直接丢弃。
- 不检查会导致松弛错误：用过期距离去更新邻居，算出的路径比实际长
- 不重插新条目会导致漏更新：队列里没机会再拿到更优距离
- 时间复杂度仍是
O((V + E) log E)，实践中E通常 ≈V²，但常数可控
邻接表怎么建才适配 Dijkstra 的松弛操作？
推荐用 vector：外层索引是起点 u，内层每个 pair 表示边 u → v 权重为 weight。注意权重在前还是在后不重要，但必须和 priority_queue 的比较逻辑一致。
常见翻车点是把 pair 写成 pair 却没改 priority_queue 的排序——默认按 first 升序，而我们希望小距离优先，所以应让距离为 first：
priority_queue<pair int>, vector<pair int>>, greater<pair int>>> pq;
// 这样 push({dist[v], v}) 才能正确排序
</pair></pair></pair>
- 如果图是无向的，记得双向加边：
adj[u].push_back({w, v}); adj[v].push_back({w, u}); - 边权必须 ≥ 0，否则 Dijkstra 不成立；负权请换 Bellman-Ford 或 SPFA
- 顶点编号建议从 0 开始，避免数组越界或离散化开销
初始化 dist[] 数组时，用 INT_MAX 还是 1e9+7？
用 INT_MAX 有风险：做 dist[u] + w 时可能整数溢出，触发未定义行为。尤其当边权较大（比如 1e9）且路径含多条边时，INT_MAX + 1 就崩了。
更安全的做法是设一个明显大于所有可能最短路径的上界，比如 1e18（对 long long）或 1e9+10（对 int，前提是总路径 ≤ 1e9）。
- 别用
-1表示未访问——没法参与min()比较，也容易和真实距离混淆 - 源点
dist[src] = 0必须在pq.push({0, src})前完成，否则第一次取出来就是错的 - 如果最终
dist[t]仍为初始大值，说明不可达，不是算法错了
松弛操作里，为什么只在 dist[v] > dist[u] + w 时才更新？
这是 Dijkstra 正确性的核心约束：仅当发现更短路径时才推进。写成 >= 会多插无效节点，增加队列负担；写成 则逻辑反了，永远进不去分支。
还要注意：更新 dist[v] 后必须立刻 pq.push({dist[v], v})，不能等下一轮循环——因为优先队列不维护内部一致性，旧条目不会自动失效。
- 漏 push 是最隐蔽的 bug，现象是某些点距离始终不更新，尤其在稀疏图中不易察觉
- 如果需要输出路径，额外维护
prev[v] = u即可，和松弛同步更新 - 多源最短路？别套 Dijkstra——考虑建超级源点，或直接用 Floyd（小规模）或多次 Dijkstra（大规模）
Dijkstra 的优先队列优化版真正难的不是写几行代码，而是理解“延迟更新”和“重复入队”是设计使然，不是缺陷。很多人卡在调试时盯着队列里一堆重复 v 疑惑，其实只要懒删除逻辑写对，它就稳。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
