迪杰斯特拉算法需用最小堆，std::priority_queue默认最大堆，必须显式指定std::greater<T>比较器；pair的first须为距离、second为节点编号以保证字典序正确；需跳过过期条目，即弹出时检查d==dist[u]。
std::priority_queue 默认是最大堆，迪杰斯特拉需要最小堆
直接用 std::priority_queue 声明不加模板参数，默认按 std::less<T> 比较，也就是大根堆 —— 会把距离最大的节点优先弹出，完全违背迪杰斯特拉“每次取当前最近未访问节点”的核心逻辑。
必须显式指定比较器为 std::greater<T>，让它变成小根堆。注意：这要求元素类型支持 operator>，或你提供自定义仿函数/lambda（但 lambda 不能直接用于模板参数，所以通常用 std::greater 或结构体）。
- 正确写法：
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
-
std::pair<int, int>的默认operator>按字典序比较：先比 first（距离），再比 second（节点编号）。只要 first 是距离，就天然满足最小堆需求 - 别写成
std::less<...>，那是反的
pair 的 first 必须是距离，second 是节点编号
因为 std::priority_queue 只看 pair 的字典序，而字典序比较时 first 优先级最高。如果把节点放前面、距离放后面，堆会按节点编号排序，完全失效。
- ✅ 正确：
std::make_pair(dist[u], u)—— 距离在前，节点在后 - ❌ 错误：
std::make_pair(u, dist[u])—— 堆只按u排，和距离无关 - 插入前确保
dist[u]是当前已知最短距离（松弛后更新）
不能依赖 priority_queue 删除旧状态，必须手动跳过过期条目
std::priority_queue 不支持修改或删除中间元素。当发现更短路径时，你只能把新 (new_dist, v) 入队，但旧的 (old_dist, v) 仍留在堆里。如果不处理，后续可能重复松弛、算错结果、甚至死循环。
立即学习“C++免费学习笔记（深入）”；
标准做法是：每次 pq.top() 取出后，立刻检查 dist[node] == current_dist。若不等，说明该条目已过期，pop() 后 continue。
- 示例关键逻辑：
while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d != dist[u]) continue; // 过期条目，跳过 for (auto &[v, w] : graph[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } - 这个判断必须放在
pop()之后、任何处理之前 - 漏掉它，算法在含重边或多次更新的图上大概率出错
初始化与图表示影响实际写法
没有统一“最佳图结构”，但常见组合会影响代码简洁性：
- 邻接表推荐用
std::vector<std::vector<std::pair<int, int>>>：外层索引是起点，内层每个pair<to, weight> -
dist数组必须初始化为一个足够大的数（如INT_MAX / 2），避免加法溢出；别用INT_MAX直接加权值 - 起点
dist[src] = 0，并立即pq.push({0, src}) - 如果图稀疏（边数 m ≈ n），
std::priority_queue版本复杂度是O((n + m) log m)；稠密图可考虑手写堆或std::set，但通常没必要
if (d != dist[u]) continue 看似简单，漏掉一次，调试半小时。 
