错误源于优先队列默认最大堆且未跳过过期节点：需用std::greater构建最小堆，并在pop后检查d!=dist[u]以跳过重复入队的过期条目。
用 std::priority_queue 实现 Dijkstra 时为什么老是得到错误距离？
核心问题往往出在优先队列的比较逻辑和节点重复入队上。C++ 的 std::priority_queue 默认是最大堆，而 Dijkstra 需要每次取当前最小距离节点，必须用 std::greater<:pair int>> 或自定义比较器；更关键的是，不能因为某个节点已出队就忽略后续更小距离的入队——Dijkstra 允许同一节点多次入队，但只处理第一次出队（即最小距离那次），后续重复出队需直接跳过。
常见错误现象：dist[v] 值比实际最短路径大，或算法提前终止、漏更新邻居。
- 初始化
dist数组全部为INT_MAX，起点设为0 - 优先队列存
std::pair：第一个是距离（用于排序），第二个是节点编号 - 每次
pop后检查if (d != dist[u]) continue;，跳过过期条目 - 松弛操作中，仅当
dist[u] + w 才更新并push
邻接表怎么建才适合 Dijkstra？vector>> 还是 vector？
用 vector 更合适：第一维是节点编号，第二维每个 pair 存 {neighbor, weight}。它内存连续、遍历快，且天然支持按序访问所有出边——这正是 Dijkstra 松弛时需要的。
vector 虽然支持 O(1) 查重边，但实际 Dijkstra 不需要查重边，反而因哈希开销和缓存不友好拖慢性能；而且无法保证遍历顺序，对调试也不友好。
建图示例：
int n = 5; // 节点数 vector<vector int>>> graph(n); graph[0].emplace_back(1, 2); // 0→1 权重 2 graph[0].emplace_back(2, 5); // 0→2 权重 5 graph[1].emplace_back(2, 1); // 1→2 权重 1 </vector>
负权边出现时 dijkstra() 突然跑出错结果，是不是实现有 bug？
不是 bug，是 Dijkstra 本身就不支持负权边。只要图中存在任意一条负权边，Dijkstra 的贪心前提（已确定最短距离的节点不会再被更短路径更新）就失效。此时即使代码语法完全正确，结果也大概率错误。
典型表现：某个节点的 dist 值在后期又被更小值覆盖，但算法早已将其标记为“已完成”并跳过后续更新。
- 遇到负权边，必须换算法：用
SPFA（已不推荐）或Bellman-Ford - 如果只有负权边但无负环，且图较稀疏，
0-1 BFS或分层图也可考虑 - 用
assert在输入后扫一遍边：若发现w ，直接报错或切换算法
从起点到终点的路径怎么还原出来？只记 dist[] 不够
必须额外维护一个 prev[] 数组（或 parent[]），在每次成功松弛 dist[v] 时记录 prev[v] = u。注意：只在 dist[u] + w 成立时更新 prev[v]，且这个赋值和 dist[v] 更新必须成对出现。
路径还原是倒序的：从终点开始，不断取 prev[v] 直到回到起点，再反转容器即可。别忘了起点的 prev[start] = -1 或其他哨兵值作为终止条件。
示例片段：
vector<int> prev(n, -1);
// ... 在松弛时：
if (dist[u] + w path;
for (int v = end; v != -1; v = prev[v]) {
path.push_back(v);
}
reverse(path.begin(), path.end());
</int>
实际写的时候，最容易被忽略的是「跳过过期队列元素」那行判断——少了它，时间复杂度会退化，结果也可能错；还有就是 prev 数组的初始化和更新时机，一不留神就指回了错误父节点。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
