错误距离主因是std::priority_queue默认大顶堆且不支持降键，须用std::greater构造小顶堆，并在pop后加if(d != dist[u]) continue跳过过期节点。
用 std::priority_queue 实现 Dijkstra 时为什么老得到错误距离？
核心问题往往出在优先队列的比较逻辑和节点重复入队上。C++ 默认 std::priority_queue 是最大堆，而 Dijkstra 需要每次取当前最小距离节点，必须用 std::greater<:pair int>></:pair> 或自定义比较器；更关键的是，不能在入队前检查是否已访问——因为松弛过程中同一节点可能被多次加入队列，得靠出队时跳过过期条目来处理。
推荐写法是：维护一个 dist[] 数组记录最短距离，每次从堆中取出 (d, u) 后，先判断 d != dist[u] 就直接 continue，避免用旧状态更新邻居。
- 别用
std::priority_queue<:pair int>></:pair>默认构造，它会把最大距离弹出来 - 图用邻接表（
vector<vector int>>></vector>），第二项是边权，别反了 - 初始化
dist全为INT_MAX，起点设为0，否则第一次松弛就失败
std::priority_queue 的比较器怎么写才不翻车？
两种安全写法：一种是显式传 std::greater（C++14+ 支持），另一种是写 lambda 并用 decltype 声明类型（C++11 起可用）。千万别写成 priority_queue<pair>, vector<...>, greater<pair>>></pair></...></pair> ——greater<pair>></pair> 比较的是字典序，不是按第一个元素比，会导致顺序错乱。
正确示例：
using pq_node = pair<int int>; // (dist, node) priority_queue<pq_node vector>, greater<pq_node>> pq;</pq_node></pq_node></int>
或者 C++11 兼容写法：
auto cmp = [](const pq_node& a, const pq_node& b) { return a.first > b.first; };
priority_queue<pq_node vector>, decltype(cmp)> pq(cmp);</pq_node>
稀疏图和稠密图下要不要换算法？
Dijkstra 在稀疏图（E ≈ V）下用堆是 O((V+E) log V)，完全够用；但若图极稠密（比如邻接矩阵存的完全图，E = V²），堆版本反而不如朴素 O(V²) 版本——因为堆操作常数大，且每条边都触发一次 push 和可能的 pop。这时直接用数组找最小未访问节点更稳。
- 边数
E → 优先用堆优化版 - 顶点数
V 且图密集 → 直接二维数组 + 线性扫描最小值更简单可靠 - 有负权边？立刻停手——Dijkstra 不适用，改用
SPFA或Bellman-Ford
实际跑不通时先查哪几个地方？
常见卡点不是算法逻辑，而是工程细节：边权类型和 dist 数组类型不一致（比如边用 int、dist 用 long long 却没统一），或图是无向图却只建单向边，或顶点编号从 1 开始但数组开小了越界。
- 打印前 3 次出队的
(d, u)，看是否按距离递增顺序 - 检查所有边权是否 ≥ 0，哪怕只有一个负数，整个结果无效
- 确认输入的顶点数
n和循环范围（如for (int i = 1; i ）是否匹配编号习惯 - 用小样例（3~4 个点）手推，对比程序输出的
dist数组每一轮变化
最易忽略的是：没把起点加入优先队列，或者加入时用了错误的距离值（比如写了 push({1, s}) 而不是 {0, s}）。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
