正确实现dijkstra需用std::priority_queue配合懒删除：存{dist[u],u}，弹出时检查dist[u]是否最新；距离数组初始化为0x3f3f3f3f（或llong_max/3），邻接表建图注意0-based索引和无向边双向添加，路径还原需prev[]数组。
怎么用 std::priority_queue 正确实现 Dijkstra 的优先队列
不能直接用 std::priority_queue<:pair int>></:pair> 存 {dist[u], u} 然后改距离——它不支持减小键（decrease-key），一旦 dist[u] 变小，旧的堆内元素不会自动更新，导致重复松弛或跳过更优路径。
实际做法是「懒删除」：每次从堆里弹出时，先检查当前取出的 dist[u] 是否等于最新已知距离。不等就跳过。
- 必须用
vector<long long></long>或vector<int></int>存最短距离，初始化为大数（如LLONG_MAX / 2），避免溢出 -
std::priority_queue默认是最大堆，要改成最小堆得写priority_queue<pair>, vector<pair>>, greater<pair>>></pair></pair></pair> - 图用邻接表存，
vector<vector int>>></vector>，第二维是{v, weight}
为什么 INT_MAX 做初始距离容易崩
加法溢出。比如某条边权是 INT_MAX，而你写 dist[u] + w，哪怕 dist[u] 已经是 INT_MAX，结果就是负数，后续比较全乱。
- 推荐用
0x3f3f3f3f（约 10.6 亿）代替INT_MAX：它足够大、可安全相加两次不溢出、还能用memset(dist, 0x3f, sizeof dist)初始化 - 若边权可能 > 10⁹，改用
long long和LLONG_MAX / 3，别直接用LLONG_MAX，加法仍可能越界 - 初始化后记得设
dist[start] = 0，否则起点距离不对，整个算法失效
邻接表建图时常见的索引错误
输入点编号从 1 开始，但代码里用 0-based 数组，没减 1 → 访问越界或算错邻居。
立即学习“C++免费学习笔记（深入）”；
- 读入边
u v w后，立刻转成u--, v--再存入邻接表 - 如果题目说“n 个点，m 条边”，数组大小必须开到
n+1（哪怕你用 0-based），否则第 n 个点存不下 - 无向图要加两条边：
g[u].push_back({v, w})和g[v].push_back({u, w})；漏掉一条，路径就不连通
输出路径时怎么反向还原节点序列
Dijkstra 本身只算距离，要路径就得额外维护 prev[] 数组记录每个点是从谁更新来的。
- 松弛成功时（
dist[v] > dist[u] + w），同步更新prev[v] = u - 还原路径用栈或递归：从终点不断跳
prev[v]，直到prev[v] == -1（起点） - 注意：起点的
prev[start]必须初始化为-1，否则还原会死循环 - 如果只需求最短距离，别浪费空间和时间存
prev；但一旦要路径，这个数组不能省
Dijkstra 对负权边完全失效，这点很容易被忽略——哪怕只有一个负权边，算法就可能给出错误结果。真要处理负权，得换 Bellman-Ford 或 SPFA，不是调几个参数能补救的。