std::priority_queue不能直接用于Dijkstra，因其默认为大顶堆且不支持降键操作；必须用std::greater<pair<int,int>>构造小顶堆，并在pop后加if(d != dist[u]) continue跳过过期节点。
std::priority_queue 为什么不能直接当 Dijkstra 的堆用
它默认是大顶堆，而 Dijkstra 需要每次取当前最小距离的节点 —— 你得先翻转比较逻辑。更关键的是，std::priority_queue 不支持修改已有元素的优先级（即“降键操作”），而 Dijkstra 在松弛边时经常要更新某个节点已入队但尚未出队的距离值。
常见错误现象：std::priority_queue 里塞了多个相同节点的不同距离，靠重复入队模拟更新，但没做去重判断，导致同一个节点被多次处理，结果错误或超时。
- 必须配合
visited数组或集合，在pop后立刻检查是否已处理过该节点 - 入队时不删旧项，只追加新距离；出队时跳过已访问过的节点
- 声明方式得写成：
std::priority_queue<:pair int>, std::vector<:pair int>>, std::greater<:pair int>>></:pair></:pair></:pair>，否则最小距离不会在堆顶
怎么写一个能跑通的 Dijkstra 版本
核心是把 (dist[u], u) 当作堆元素，按距离升序排列。初始化所有距离为 INT_MAX，源点距离设为 0 并入队。每次 pop 出最小距离节点，若已访问就跳过；否则标记访问，并遍历其邻边，对满足 dist[v] > dist[u] + w 的边执行松弛：更新 dist[v] 并将 (dist[v], v) 入队。
示例片段（邻接表存图）：
立即学习“C++免费学习笔记（深入）”；
vector<vector<pair<int, int>>> graph(n); // {neighbor, weight}
vector<int> dist(n, INT_MAX);
dist[src] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // 常见坑：没这句就会处理过期节点
for (auto [v, w] : graph[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
性能和内存开销要注意什么
重复入队会让堆大小远超节点数，最坏情况每条边都触发一次入队，堆中最多有 O(E) 个元素。虽然时间复杂度仍是 O((V+E) log E)，但常数较大，尤其在稠密图中可能比手写堆慢 2–3 倍。
-
std::greater<pair int>></pair>比较的是 pair 的 first（距离），second（节点编号）仅用于 tie-breaking，不影响正确性 - 如果权重是 long long，务必用
pair<long long int></long>，否则溢出后比较失效 - 避免用
struct包装再自定义比较函数——增加拷贝开销，不如直接用pair
什么时候该换别的实现
当图规模大（比如 V > 1e5）、边特别多、或者需要频繁查询中间状态时，std::priority_queue 的冗余入队会明显拖慢速度。此时要么改用支持减键的斐波那契堆（C++ 标准库没有），要么用 std::set 模拟可删堆（插入/删除 O(log n)，但支持 erase 已存在元素），或者干脆上第三方库如 Boost.Graph 的 dijkstra_shortest_paths。
真正容易被忽略的点：很多人以为只要用了 priority_queue 就算“用了堆优化”，却没意识到没加 if (d > dist[u]) continue 这行，算法就退化成 O(V²) 的暴力版本，而且结果还错。
