std::priority_queue 默认是大根堆，存{dist,node}时若不重载比较逻辑为小根堆（按first升序），会优先弹出距离大的点，违背Dijkstra每次取当前最短距离节点的核心要求；且greater按字典序比较导致逻辑错误，故必须自定义比较器。
直接说结论：用实现迪杰斯特拉（Dijkstra）比手写堆或 BFS 模拟更稳，但必须重载比较逻辑、避免重复入队、初始化距离数组为（而非）——否则一跑带负权边的图就崩，哪怕你没真用负权。
为什么
默认不能直接用？
Dijkstra 要每次取「当前已知最短距离最小」的节点，而
默认是大根堆。如果你存
，不改比较规则，它会优先弹出距离大的点。
实操建议：
定义结构体或用
，但必须传自定义比较器：
然后声明：
别偷懒用
——它对
比较的是字典序，
会被认为小于
，导致逻辑错乱
如果图节点数超 10⁵，把
换成
更明确，避免平台差异
松弛操作后，要不要把新状态 push 进队列？
要，但必须无条件 push —— Dijkstra 允许同一节点多次入队，靠「首次出队即最短」来保证正确性。只在出队时检查是否已访问过，而不是入队前查重。
立即学习
“
C++免费学习笔记（深入）
”；
C知道
CSDN推出的一款AI技术问答工具
下载
常见错误现象：
入队前判断
入队前加
→ 错！
应只在
后标记，否则会跳过更优路径
用
替代
去重 → 可行但常数大，10⁵ 级图易 TLE
邻接表怎么建才不踩内存和效率坑？
用
最稳妥：第一维是起点，第二维是
。别用
，稀疏图下空间爆炸且遍历慢。
使用场景提示：
如果边是离线读入的，一次性
每个
的容量（比如总边数 / 节点数 × 2），减少 realloc
权重类型必须和距离数组一致：若边权是
，但路径可能超
，距离数组就得用
有向图和无向图仅差一行：
vs
真正容易被忽略的是：Dijkstra 不处理负权边，但很多初学者拿它跑含负权的测试样例，发现结果不对却归因为代码写错。其实只要输入里出现
std::priority_queueLLONG_MAX-1std::priority_queuestd::priority_queue{distance, node}std::pairauto cmp = [](const auto& a, const auto& b) { return a.first > b.first; };std::priority_queue, std::vector>, decltype(cmp)> pq(cmp); greaterpair{5, 100}{10, 1}long longint64_tif (new_dist 再 push → 正确，但漏掉「相同距离不同路径」的调试信息，不影响结果if (visited[v]) continuevisitedpq.pop()setpriority_queuevector>> {to_node, weight}map> reserve()adj[u]intINT_MAXlong longadj[u].push_back({v, w});adj[u].push_back({v, w}); adj[v].push_back({u, w});weight ，就该立刻换 SPFA 或 Bellman-Ford —— 这不是实现问题，是算法前提失效。