因为std::priority_queue不支持动态更新节点权重，只能插入新副本，若不检查dist[u]是否过期（pop时加if(d != dist[u]) continue），就会用过期距离松弛邻边导致最短路径计算错误。
为什么直接用 priority_queue 实现 Dijkstra 容易出错
因为 priority_queue 不支持动态更新节点权重，一旦某个节点的最短距离被更新，旧的“过期”条目仍留在队列里。如果不做处理，会重复松弛、多算、甚至得到错误结果。
常见错误现象：distance[v] 已更新为更小值，但队列中还存在 (old_dist, v)，后续又用它去松弛邻居，导致路径变长或循环判断。
- 必须在取出元素时检查是否已访问（即
dist[u] 成立就跳过） - 不能依赖队列“自动去重”，要靠手动过滤
-
priority_queue<pair int>></pair>默认是大顶堆，需用greater或取负数来模拟小顶堆
邻接表怎么建才适合 Dijkstra 的频繁访问
用 vector<vector int>>></vector>（即 graph[u] 存 (v, weight)），比邻接矩阵省空间、遍历快，尤其适合稀疏图。
注意：边权必须非负，否则 Dijkstra 失效——这是算法前提，不是实现问题；若含负权，请换 Bellman-Ford 或 SPFA。
- 索引从 0 开始还是 1 开始，要和输入统一，别让
graph[0]对应第 1 个点却漏掉第 0 个点 - 如果输入有重边，建图时建议保留最小权重那条（
min覆盖），或在松弛时自然淘汰 - 不要用
map<int vector>></int>做邻接表——哈希开销大，且无序遍历影响缓存局部性
dist[] 初始化为什么不能全设为 INT_MAX
直接赋 INT_MAX 后做 dist[u] + w > dist[v] 判断，可能溢出：当 dist[u] == INT_MAX 时，加正数会绕回负数，条件恒真，引发越界写入或逻辑崩溃。
正确做法是用一个明显大于所有可能路径和的值，比如 1e9 + 7 或 LLONG_MAX / 2（若用 long long）。
- 初始化
dist[src] = 0，其余为大数；别漏掉起点 - 如果图中最大边权是
W、最多V个点，则最坏路径长度 ≤W * (V - 1)，据此选安全上界 - 比较时写成
if (dist[u] != INF && dist[u] + w ，避免溢出参与运算
如何输出最短路径本身，不只是长度
Dijkstra 只保证算出最短距离，路径需额外记录前驱节点。每次成功松弛 v 时，记下 prev[v] = u，最后从终点倒推即可。
注意：多个最短路径时，prev[] 只保存其中一条；如需全部路径，得改用 DFS/BFS 在最短距离约束下枚举，复杂度陡增。
- 用
vector<int> prev(n, -1)</int>初始化，-1 表示未访问或无前驱 - 重建路径时用栈或逆置 vector，避免递归（防爆栈）
- 如果只查单次路径，别在主循环里反复构造 vector——先存
prev，需要时再恢复
最麻烦的其实是边界：起点不可达时 prev[dst] 仍是 -1，得提前判断；图不连通时部分 dist[i] 保持初始大值，别误当有效距离输出。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
