因为std::priority_queue不支持动态修改已入队元素优先级（即无法减小键），Dijkstra松弛时需更新节点距离，只能重复入队新副本；若不检查dist[u]是否过时（pop时加if(d != dist[u]) continue），就会用过期距离错误松弛邻边。
为什么直接用 std::priority_queue 会出错？
因为 std::priority_queue 不支持动态修改已入队元素的优先级（即无法执行“减小键”操作），而 Dijkstra 算法在松弛边时可能需要更新某个节点的当前最短距离。如果强行插入重复节点而不去重，会导致同一节点被多次处理，时间复杂度退化为 O(E log E) 甚至更差，且逻辑易错。
- 正确做法是允许重复入队，但每次从堆中取出时检查是否已被更优路径更新过——即维护一个
dist[]数组，取出节点u后先判断dist[u] != current_distance，若不等则跳过 - 使用
std::priority_queue<:pair int>, vector<pair int>>, greater<pair int>>></pair></pair></:pair>表示小根堆，其中pair<distance node></distance> - 初始化时把起点入堆：
q.push({0, start})，dist[start] = 0
邻接表怎么建才适合 Dijkstra？
必须用「起点→（终点，边权）」的结构，不能只存终点。C++ 推荐用 vector<vector int>>></vector>，外层下标是节点编号，内层每个 pair<int int></int> 表示 {to_node, weight}。
- 无向图要双向加边：
graph[u].push_back({v, w}); graph[v].push_back({u, w}); - 有向图只加单向：
graph[u].push_back({v, w}); - 注意节点编号是否从 0 开始——若输入是 1-indexed，建图前统一减 1，避免数组越界
- 边权必须 ≥ 0，否则 Dijkstra 不适用；遇到负权边应换用 Bellman-Ford 或 SPFA
如何避免 INF 溢出和比较错误？
设初始距离为无穷大时，别用 INT_MAX——因为松弛时做 dist[u] + w 可能溢出。推荐用一个明显大于所有可能路径和的常量，比如 1e9 + 10 或 0x3f3f3f3f（约 10.6 亿，且满足 0x3f3f3f3f + 0x3f3f3f3f ）。
- 初始化：
vector<int> dist(n, 0x3f3f3f3f); dist[start] = 0;</int> - 松弛判断写成：
if (dist[u] != 0x3f3f3f3f && dist[u] + w ，防止溢出参与比较 - 输出前检查：
if (dist[target] == 0x3f3f3f3f) cout 表示不可达
完整可运行的最小骨架长什么样？
以下是一个带注释、去掉冗余功能的 C++17 版本，适用于单源最短路查询（如洛谷 P4779）：
立即学习“C++免费学习笔记（深入）”；
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s;
cin >> n >> m >> s;
--s; // 转为 0-indexed
vector<vector<pair<int, int>>> graph(n);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u; --v;
graph[u].emplace_back(v, w);
}
vector<int> dist(n, 0x3f3f3f3f);
dist[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.emplace(0, s);
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.emplace(dist[v], v);
}
}
}
for (int i = 0; i < n; ++i) {
cout << dist[i] << " \n"[i == n-1];
}
}
关键点在于：重复入队不删旧、取堆顶立刻校验、邻接表存权值、INF 选得安全。真正卡住人的往往不是算法逻辑，而是这些边界细节没对齐。
