dijkstra需最小堆，std::priority_queue默认最大堆，须用std::greater或自定义比较器；路径还原需prev[]数组，负权边不适用，多终点无需重复运行，字典序路径需松弛时额外比较。
用 std::priority_queue 实现 Dijkstra 时，为什么总是得不到正确路径？
因为默认的 std::priority_queue 是最大堆，而 Dijkstra 需要每次取当前距离最小的节点；不重载比较逻辑或换容器，top() 返回的就是错的节点。
- 必须用
std::greater<:pair int>></:pair>或自定义比较器，让优先队列按距离升序排列 - 推荐写法：
std::priority_queue<:pair int>, std::vector<:pair int>>, std::greater<:pair int>>></:pair></:pair></:pair> - 别把
distance和node_id顺序写反——pair<dist node></dist>才能靠 first 正确比较 - 如果图稀疏但用了邻接矩阵，会超时；稠密图才适合矩阵，否则务必用邻接表（
vector<vector int>>></vector>）
如何还原最短路径，而不是只算出最短距离？
单纯更新 dist[] 数组只能知道长度，要路径就得记录前驱。Dijkstra 本身不天然支持路径回溯，得手动维护 prev[] 数组。
- 初始化
prev[i] = -1，松弛成功时立即更新：prev[v] = u（u → v 是更优边） - 路径还原用栈或递归逆序输出，避免 vector insert(0, …) 导致 O(n²) 复杂度
- 注意：
prev只在松弛成功时更新，不是每次访问都改；重复入队的节点不会覆盖已确定的前驱 - 如果起点到某点不可达，
prev[end]仍是 -1，别直接解引用
遇到负权边就崩，是算法写错了还是理解错了？
Dijkstra 从数学上就不支持负权边——一旦某个节点被标记为“已确定最短距离”，后续就不再检查，而负权边可能提供更短路径，导致结果错误。
- 运行时不会报错，但输出距离明显偏大，或
prev指向形成环（比如 A→B→A） - 确认图中是否存在负权边：读入边权重后加个断言
assert(w >= 0)，调试阶段很有用 - 真有负权且无负环，该换
Bellman-Ford或SPFA；有负环则最短路径无定义 - 别试图“修复”Dijkstra 来处理负权——它不是 bug，是能力边界
多终点 / 路径唯一性 / 重建路径时内存爆炸怎么办？
原始 Dijkstra 是单源单终点思维，但实际常需查多个终点距离、或要求字典序最小路径、或图极大时存不下完整 prev 数组。
立即学习“C++免费学习笔记（深入）”；
- 多终点：跑一遍 Dijkstra 就够了，所有
dist[end_i]都有效，不用反复调用 - 字典序最小路径：松弛时加一层判断——距离相等时，比较
prev[u]对应的路径字典序，但这要存整个路径串，代价高；更实用的是在松弛条件里加|| (dist[v] == dist[u] + w && prev[v] > u) - 内存受限：不用全局
prev[]，改用“按需重建”——每个查询终点时，从该点倒推，用哈希表或临时数组存已访问过的前驱，避免存全部 - 注意：
prev数组大小必须 ≥ 节点数，下标从 0 开始就别用 1-based 初始化漏掉 index 0
事情说清了就结束