Dijkstra必须用priority_queue配合邻接表以达O((V+E)log V)复杂度；优先队列保证取最小距离节点为O(log V)，邻接表确保只遍历真实存在的边；需接受重复入队并跳过过期节点。
为什么 dijkstra 一定要用 priority_queue 配合邻接表？
不用优先队列的朴素 dijkstra 时间复杂度是 O(V²)，对点数超 10⁴ 的图基本不可用；而用 std::priority_queue + 邻接表可压到 O((V+E) log V)。关键在于：每次取最小距离节点必须是 O(log V)，且只遍历真实存在的边（邻接表保证 E 级别访问），不是全扫数组。
常见错误是把 priority_queue 当成“自动更新堆顶”的容器——它不支持修改已有元素的值，所以必须接受重复入队：当发现更短路径时，直接 push 新二元组 {dist, node}，旧的会在后续被 pop 时跳过（靠 if (dist[node] 过滤）。
priority_queue 的比较规则怎么写才不翻车？
C++ 默认是大根堆，但我们要的是“距离最小的先出”，所以必须自定义比较器。最稳妥写法是用仿函数或 lambda，且注意：不能直接写 greater<pair>></pair>，因为 pair 比较先比 first，而我们希望 first 是距离，所以要让小距离排前面——即“less”语义，但 priority_queue 的模板参数是“谁该被优先弹出”，所以实际要传入「大于」逻辑（即当 a > b 时，a 应该后出，b 先出）。
- 推荐写法：
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
- 等价但更清晰的 lambda 写法（C++11+）：
auto cmp = [](const pair<int,int>& a, const pair<int,int>& b) { return a.first > b.first; };<br>priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp); - 错误示范：
priority_queue<pair>></pair>（大根堆，会先弹出最大距离）
邻接表怎么建？vector<vector>>></vector> 还是 vector<list>></list>？
用 vector<vector>>></vector> 是最常用且高效的选择：第一维是起点编号，第二维每个 pair<to weight></to> 表示一条有向边（无向图就双向加）。它缓存友好、随机访问快、构造简单。除非边数极少且频繁删边，否则别用 list 或 map。
立即学习“C++免费学习笔记（深入）”；
注意权重类型：如果题目给的是非负整数，用 int；若可能超 INT_MAX 或含浮点，需统一换成 long long 或 double，并同步改 dist 数组和 priority_queue 中的类型。
建边示例（无向图）：
vector<vector<pair<int, int>>> graph(n);<br>// 加边 u->v 权重 w<br>graph[u].emplace_back(v, w);<br>graph[v].emplace_back(u, w);
初始化、松弛、跳过失效节点这三步最容易漏哪？
三个关键动作必须严格按序，缺一不可：
- 初始化：
dist数组全设为INT_MAX（或LLONG_MAX），dist[src] = 0，然后pq.push({0, src}) - 松弛：对当前节点
u的每条出边(u→v, w)，若dist[u] + w ，则更新 <code>dist[v]并pq.push({dist[v], v}) - 跳过失效节点：在
while (!pq.empty())循环开头，auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue;—— 这行不能省，否则会处理过期状态，导致结果错误或超时
特别注意：dist 数组必须是全局可见的（比如函数内 vector<long long> dist(n, LLONG_MAX)</long>），不能用局部临时变量覆盖；且所有涉及距离比较的地方，类型必须与 dist 一致，避免隐式转换截断。
真正卡住人的往往不是算法逻辑，而是类型不匹配、堆比较器反了、或者忘了跳过过期节点——这三处任一出错，结果就完全不对，还很难 debug。
