std::priority_queue 默认不支持降键操作，导致Dijkstra中松弛时无法更新节点优先级；需用懒删除：弹出时检查距离是否过时，过时则跳过。
为什么 std::priority_queue 默认不能直接用于 Dijkstra？
因为 std::priority_queue 不支持修改已入队节点的优先级（即“降键”操作），而 Dijkstra 在松弛过程中常需更新某节点当前最短距离。若强行插入新状态而不移除旧状态，会导致队列中存在多个同一节点的不同距离值——后续可能重复处理过时的高距离条目。
解决思路不是改队列，而是「懒删除」：每次从队列弹出时，先检查该距离是否已过时（即大于当前已知最短距离）。若过时，直接跳过。
- 用
vector<long long></long>或vector<int></int>存最短距离，初始化为大数（如LLONG_MAX） - 优先队列元素类型推荐
pair<long long int></long>：第一项是距离，第二项是节点编号；默认按 first 升序排，所以要用greater<pair long int>></pair>或自定义比较器 - 不要用
make_heap+push_heap手动维护，复杂度和可读性都不如priority_queue+ 懒删除
如何写一个安全、可复用的 Dijkstra 函数？
关键在于接口清晰、边界可控、不依赖全局变量。建议封装为接受邻接表、起点、节点总数的函数，返回 vector<long long></long> 距离数组。
邻接表用 vector<vector long>>></vector>：外层索引是起点，内层每个 pair 是 {to, weight}。注意边权必须 ≥ 0，否则 Dijkstra 不适用。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 起点距离设为 0，其余初始化为
LLONG_MAX / 2（避免后续加法溢出） - 队列初始只 push
{0, start} - 循环中每次
pop后，先判断dist[u] != current_dist，成立则 continue - 对每个邻边
v，若dist[u] + w ，则更新 <code>dist[v]并push {dist[v], v}
vector<long long> dijkstra(const vector<vector<pair<int, long long>>>& graph, int start, int n) {
vector<long long> dist(n, LLONG_MAX / 2);
dist[start] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
pq.push({0, start});
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});
}
}
}
return dist;
}
常见报错和性能陷阱
最典型的是运行时崩溃或结果错误，往往源于以下几点：
-
graph大小不等于n，或某条边的to节点编号越界（如v >= n），访问dist[v]会越界 - 边权用了
int但累加后超INT_MAX，导致距离变成负数，破坏堆序；务必统一用long long存距离和边权 - 忘记在
push前检查dist[u] + w < dist[v]，盲目 push 会大幅增加队列大小，最坏退化为 O(E log E) - 使用
priority_queue<pair<int, int>>且未指定greater，结果是最大堆，第一个元素是最大距离，算法立即失效
什么时候不该用这个版本的 Dijkstra？
当图稀疏（E ≈ V）且需要频繁查询任意两点最短路径时，单源 Dijkstra 仍要跑 V 次，总复杂度 O(V² log V)，不如 Floyd（O(V³)）或预处理 + LCA（树上）等方案。
更关键的是：如果图中存在负权边，哪怕没有负环，这个实现也会给出错误结果——Dijkstra 本质不支持负权，此时应换 SPFA（已不推荐）或 Bellman-Ford，或确认是否真能转为非负（如 Johnson 算法）。
另外，若节点编号不连续（如 ID 是字符串或大整数），别硬套数组下标，改用 unordered_map<Key, long long> 存距离，队列也存 pair<long long, Key>，但哈希开销和代码复杂度会上升。
