邻接表+优先队列是实际首选，因空间高效（如1000点2000边仅需约16KB）、遍历只访问真实邻居，避免邻接矩阵在稀疏图中99.8%无效存储和整行扫描的低效。
直接用 std::priority_queue 配邻接表，别碰邻接矩阵——除非图稠密到边数接近顶点数平方，否则纯浪费内存和时间。
为什么邻接表 + priority_queue 是实际首选
邻接矩阵在 1000 个点、2000 条边的稀疏图里，要开 graph[1000][1000]，占 4MB 内存，但 99.8% 的位置是无效的 INT_MAX；而邻接表只存真实边：vector<vector int>>></vector>，空间约 2000 × 2 × sizeof(int) ≈ 16KB。遍历时也只扫邻居，不是整行扫描——Dijkstra 每次松弛只关心“谁跟我连”，不是“谁没跟我连”。
常见错误现象：for (int v = 0; v 这种写法在稀疏图中每次循环都做 1000 次判断，O(V²) 稳稳坐实；换成邻接表后，内层循环次数 = u 的出度，总复杂度降为 O((V+E) log V)。
- 有向图建边：只调用一次
graph[u].push_back({v, w}) - 无向图建边：必须补上
graph[v].push_back({u, w})，漏掉就变成单向了 - 权重必须 ≥ 0；一旦出现
w ，<code>Dijkstra会跳过更优路径，结果不可信
priority_queue 怎么初始化才不取错最小值
C++ 默认是大顶堆，top() 返回最大元素——但 Dijkstra 必须每次取距离最小的节点。不改比较器，算法从第一步就崩。
立即学习“C++免费学习笔记（深入）”；
正确写法：priority_queue<pair int>, vector<pair int>>, greater<pair int>>></pair></pair></pair>。注意三点：
-
pair必须是pair<distance node></distance>，不能把node放前面，否则greater比的是node编号而非距离 - 别用
less或缺省模板参数，那还是大顶堆 - 入队前不用检查该节点是否已在队列里——同一节点可能因不同路径多次入队，靠出队时判重即可
松弛操作（relax）的三步闭环不能断
松弛不是“看到能更新就 push”，而是“发现更短路径 → 更新 dist[v] → 立即 push 新状态”。断掉任意一环，后续节点就收不到更优解。
标准写法：
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
容易踩的坑：
-
dist初始值不能直接用INT_MAX：INT_MAX + w会溢出成负数，导致误更新；推荐用INT_MAX / 2或1e9（确保加权后不溢出） - 起点必须在初始化阶段设
dist[start] = 0，且立刻pq.push({0, start})；漏掉这句，整个队列为空，算法直接结束 - 出队后第一句必须是
if (d != dist[u]) continue;——这是去重唯一可靠方式；依赖visited[]数组反而容易出错，因为 Dijkstra 不靠它判定“已确定”，而靠dist是否已被更小值覆盖
路径还原只需加一个 parent 数组
如果不仅要距离，还要具体路径，就在松弛时同步记录前驱：parent[v] = u。不需要额外数据结构，也不影响核心逻辑。
回溯示例：
vector<int> path;
for (int v = target; v != -1; v = parent[v]) {
path.push_back(v);
}
reverse(path.begin(), path.end());
注意点：
-
parent数组初始全填-1，起点的parent[start] = -1（无前驱） - 只有成功松弛时才更新
parent[v]，不是每次访问都赋值 - 若
dist[target]仍是初始大数，说明不可达，此时path只含起点或为空，别硬回溯
最易被忽略的是溢出防护和出队判重——这两处一错，结果看似运行正常，实则路径长度错得离谱，且极难定位。别省那两行代码。
