spfa 应使用 std::queue；std::deque 易引发未同步更新 in_queue[] 的 bug，且 slf 优化需额外逻辑而非仅换容器。松弛时须先判断 dist[u] + w
SPFA 用
std::queue还是std::deque？SPFA 的核心是“队列优化的 Bellman-Ford”，但队列类型直接影响正确性和性能。用
std::queue是标准做法；std::deque没必要，还容易误写成“SLF 优化”却没配对实现，反而引入 bug。常见错误现象：
std::deque被随手 push_front 试图加速，但没同步更新入队标记（in_queue[]），导致节点重复松弛、无限循环或结果错误。
- 只用
std::queue，保持 FifO 语义，逻辑清晰、不易出错- 若真要 SLF（Small Label First）优化，必须同时维护
in_queue[]和比较逻辑，不是换容器就能生效- 在稀疏图上，
std::queue的常数足够小；别过早优化容器
dist[v] > dist[u] + w判断里要不要加!in_queue[v]？要加，而且必须放在松弛成功之后再入队，顺序不能反。
典型错误：先判断
!in_queue[v]再检查是否能松弛，导致已入队但尚未处理的节点被跳过，漏掉更短路径。立即学习“C++免费学习笔记（深入）”；
- 正确顺序：先算
if (dist[u] + w ，成立则更新 <code>dist[v]，再检查if (!in_queue[v])，成立才q.push(v)并置in_queue[v] = truein_queue[]标记的是“当前在队列中”，不是“曾经入过队”——重复入队无意义，还拖慢性能- 数组大小必须和点数一致，下标从 1 开始就别用
vector[0]存无效值怎么检测负环？
SPFA 本身不保证检测所有负环，但可用入队次数做实用判断：某个点入队 ≥ n 次，基本可断定存在负环。
注意这不是数学证明，而是工程经验阈值。标准 Bellman-Ford 是 n−1 轮松弛，SPFA 中单点被松弛超过 n 次，说明路径上必有环，且该环为负。
- 开一个
cnt[]数组，每次v入队时cnt[v]++- 入队前加判断：
if (cnt[v] >= n) { return true; }- 别用
cnt[v] > n—— 等到 >n 才触发，可能已经死循环了- 负环检测会略微增加内存和分支开销，仅在需要时开启（比如题目明确要求判负环）
邻接表用
vector<pair int>></pair>还是结构体？用
vector<pair int>></pair>足够，更轻量、缓存友好，尤其点数多但边不稠密时。结构体（如
Struct edge { int to, w; };）看似语义清晰，但实际编译后几乎没差别，反而容易因对齐或 vector realloc 引发隐式拷贝开销。
- 推荐写法：
vector<vector int>>> g(n + 1);</vector>，g[u].emplace_back(v, w);- 别用
map<int int></int>或unordered_map存邻接关系——SPFA 对遍历速度敏感，哈希或红黑树跳转破坏局部性- 如果边权恒为 1，可直接用
vector<vector>></vector>，省去 pair 解包，但这是特例，不具通用性边界情况比算法本身更耗时间：点编号从 0 还是 1、重边怎么处理、自环要不要跳过——这些细节不写进
dist初始化和松弛条件里，跑不出正确结果。
