应使用 std::priority_queue 而非 std::set 或手写堆，因其支持 O(log n) 入队和 O(1) 取顶、常数小；虽不支持减键，但插入新记录+忽略过期项更简洁安全；须用 std::greater 声明为小根堆，格式为 std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>, std::greater<>> pq;
为什么用 std::priority_queue 而不是 std::set 或手写堆
因为 Dijkstra 的核心是反复取当前最小距离节点，std::priority_queue 天然支持 O(log n) 入队和 O(1) 取顶，且常数小。虽然它不支持修改已有元素的优先级（即“减键”操作），但直接插入新记录 + 忽略过期记录，比用 std::set 维护迭代器或手写可删堆更简洁、不易出错。
常见错误现象：std::priority_queue 默认是大根堆，必须传入 std::greater；否则第一次弹出的就是最大距离，算法立刻失效。
- 声明方式必须是：
std::priority_queue<:pair int>, std::vector<:pair int>>, std::greater> pq;</:pair></:pair>（第一个int是距离，第二个是节点编号） - 不要试图在队列里更新已存在节点的距离——直接
pq.push({new_dist, v})，后续遇到旧记录时靠if (dist[v] 跳过 - 如果图稀疏（边数 m ≈ n），这种“懒删除”几乎无性能损失；稠密图也只多 log n 级别冗余操作
dist 数组初始化为 INT_MAX 还是 1e9+7
用 INT_MAX 有溢出风险：当某条边权很大（比如接近 INT_MAX），松弛时 dist[u] + w 可能溢出为负数，导致错误更新。实际项目中建议用一个明显大于所有可能最短路径的常量，比如 1e9+10 或 0x3f3f3f3f（约 10.6 亿，且满足 0x3f3f3f3f * 2 ）。
- 初始化写法：
std::vector<int> dist(n, 0x3f3f3f3f); dist[start] = 0;</int> - 判断是否不可达：用
if (dist[v] == 0x3f3f3f3f)，而不是== INT_MAX - 如果边权含负数，Dijkstra 本身就不适用——此时应换 SPFA 或 Bellman-Ford，别硬改初始化值
邻接表存图时，vector<vector int>>></vector> 和 vector<vector>></vector> 哪个更稳妥
前者更轻量、通用性强；后者适合需要扩展字段（如边 ID、方向标记）的场景。但绝大多数 Dijkstra 实战只要“终点 + 权重”，用 pair 就够了，且避免结构体构造/拷贝开销。
立即学习“C++免费学习笔记（深入）”；
容易踩的坑：用 vector<vector>></vector> 存两个字段（比如 {v, w}），看似省事，但读取时易写错下标（g[u][i][0] vs g[u][i][1]），可读性差，编译也不报错。
- 推荐写法：
vector<vector int>>> g(n);</vector>，加边：g[u].emplace_back(v, w); - 遍历时清晰：
for (auto [v, w] : g[u]) { ... }（C++17 结构化绑定） - 如果必须用结构体，至少定义
struct Edge { int to, w; };，别裸用vector<int></int>
单源最短路径跑完后，怎么还原具体路径
Dijkstra 本身不记录路径，得额外维护 prev 数组。每次成功松弛 dist[v] 时，同步记录 prev[v] = u。注意：只在 if (dist[u] + w 成立时更新，不是每次访问都写。
还原路径时从终点倒推，用栈或 vector 反转，别忘了起点本身也要加入结果。
- 初始化：
vector<int> prev(n, -1);</int>，起点的prev[start] = start或保持 -1 都行，但还原逻辑要一致 - 松弛时加一句：
if (dist[u] + w - 还原示例：
vector<int> path; for (int x = end; x != -1; x = prev[x]) path.push_back(x); reverse(path.begin(), path.end());</int>
复杂点在于：路径还原和距离计算是解耦的，很多人只验证了 dist[end] 正确就以为路径也对了，其实 prev 更新漏条件或初始化错，会导致路径乱序或截断。检查时最好挑一个中间节点，手动核对它的 prev 是否指向真正前驱。
