std::priority_queue实现dijkstra需用小根堆：定义pair为{dist,node}，自定义比较器使堆按距离升序；松弛时push新状态并懒删除（检查d!=dist[u]）；邻接表用vector，存{to,weight}；遇负权边必须换spfa或bellman-ford。
怎么用 std::priority_queue 实现 Dijkstra 而不写错比较逻辑
很多人卡在第一步：优先队列弹出的不是当前最短距离节点。根本原因是 std::priority_queue 默认是大根堆，而 Dijkstra 需要每次取最小距离节点。
正确做法是自定义比较器，让堆按 dist 升序排列——但别直接重载 operator，容易和别的地方冲突。推荐用 lambda 包裹的函数对象（C++20 前需用仿函数）：
auto cmp = [](const auto& a, const auto& b) { return a.first > b.first; };
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(cmp)> pq(cmp);
- 第一个
int是距离，第二个是节点编号；顺序不能反，否则比较逻辑会失效 - 必须显式传入
cmp构造，只声明类型不传值会导致编译错误（C++17 起更严格） - 别用
greater代替——它对pair比较的是字典序，不是你想要的距离优先
为什么松弛操作后不能直接修改堆里已存在的节点
Dijkstra 的核心是“发现更短路径时更新”，但 std::priority_queue 不支持修改中间元素。强行 push 新状态没问题，但旧状态还在堆里，会重复处理。
标准解法是懒删除：遇到已访问过的节点（dist[node] ）直接跳过。
立即学习“C++免费学习笔记（深入）”；
- 必须维护一个独立的
dist数组或 vector，初始化为INT_MAX或1e9+7 - 每次从堆中 pop 出来先检查
if (d != dist[u]) continue;，这是关键防线 - 不加这句，复杂度退化成 O(E log E)，甚至可能死循环（尤其有重边时）
邻接表怎么建才不翻车：vector<vector int>></vector> 还是 vector<vector>></vector>
用 vector<vector int>></vector> 最省事，但要注意 pair 的顺序：通常是 {neighbor, weight}，不是 {weight, neighbor}。
如果边数极大（比如 1e6 级别），用结构体封装可读性更好，但别为了“清晰”加虚函数或智能指针——Dijkstra 对性能敏感。
- 初始化邻接表记得预留容量：
graph.resize(n);，否则反复 push_back 可能触发多次内存重分配 - 无向图要双向加边；有向图只加一次；别漏掉权重为 0 的边（某些题会卡这个）
- 如果输入含重边，建表时不用去重——Dijkstra 自然会选最短那条，但确保没负权
遇到负权边就停手：Dijkstra 不适用，改用 SPFA 或 Bellman-Ford
只要图里存在任意一条负权边，Dijkstra 就可能算错。这不是实现问题，是算法前提被破坏了。
判断依据不是“有没有负号”，而是“是否存在从起点可达的负权环”——但实际做题时，看到负权边就该本能切换算法。
-
SPFA是Bellman-Ford的优化，用队列而非枚举所有边，但最坏仍是 O(VE) - 如果题目明确说“无负权”，那就放心用 Dijkstra；否则先扫一遍输入，检查
weight - C++ 标准库没有内置 SPFA，得自己写；别试图给 Dijkstra 加 hack（比如把负权平移），会挂得毫无征兆
真正麻烦的是稀疏图 + 负权 + 强制单源最短路——这时候得看数据范围，有时 DFS + 记忆化反而更稳，但那是另一回事了。
