SPFA 不超时的关键是严格控制入队逻辑和松弛条件：仅当距离更新成功时才入队，用 std::queue 和 in_queue[] 数组避免重复松弛，链式前向星存图，并初始化 dist[] 为极大值。
SPFA 在 C++ 里怎么写才不超时
SPFA 本质是 Bellman-Ford 的队列优化，但很多人直接套模板却在稀疏图上被卡成 O(VE)，甚至比朴素 Dijkstra 还慢。关键不是“会不会写”，而是“怎么控制入队逻辑”和“怎么避免重复松弛”。
- 用
std::queue而非std::priority_queue—— SPFA 不依赖堆序，堆反而破坏其松弛顺序优势 - 必须维护
in_queue[]数组，只让节点首次入队或距离更新后再次入队，禁止无脑push - 对每个出队节点
u，遍历其邻接边时，仅当dist[v] > dist[u] + w成立才更新，并检查v是否已在队列中 - 慎用
vector<vector int>>></vector>存图：小图没问题，但边数 > 1e5 时，连续内存访问不如链式前向星（head[],to[],w[],nxt[]）快
为什么 SPFA 会被卡、什么情况下该换 Dijkstra
SPFA 最坏复杂度仍是 O(VE)，而恶意构造的网格图、菊花图、负权环附近节点反复入队，很容易触发。它只在“存在负权边且图稀疏、负权分布分散”时有实际优势。
- 若图中无负权边，直接用
priority_queue+dijkstra()，稳定O(E log V) - 若只有少量负权边（比如 ≤ 3 条），可考虑
0-1 BFS或分层图建模，而非硬上 SPFA - 判负环时，需统计每个节点入队次数：一旦
cnt[v] >= V，立刻返回负环；但注意——cnt[]必须在每次dist[v]更新成功后才自增，不能放在入队前
std::queue 和手写循环队列有区别吗
对大多数 OJ 数据，std::queue（基于 deque）完全够用；但如果你在本地跑大规模随机图或嵌入式环境受限，手写数组模拟的循环队列能省掉动态内存分配开销。
- 手写要点：设数组大小为
MAXN，用head和tail下标，(tail + 1) % MAXN != head判满 - 别用
vector::push_back()模拟队列——每次扩容可能触发 memcpy，实测比std::queue慢 20%~40% -
std::queue默认底层是deque，支持两端操作，但 SPFA 只需 FIFO，所以无需改用list——那会增加指针跳转开销
常见编译/运行错误怎么快速定位
最常踩的坑不是算法错，而是边界没控住或初始化遗漏，导致未定义行为或 WA。
立即学习“C++免费学习笔记（深入）”；
-
dist[]初始化必须用LLONG_MAX / 0x3f3f3f3f，不能用-1或0—— 否则负权边松弛时比较失效 - 忘记清空
in_queue[]和cnt[]数组（多测时尤其致命），导致上一组数据残留影响下一组 - 邻接表遍历时写成
for (int i = head[u]; i; i = nxt[i])，但忘了初始化head[]全为0，结果第一次就跳进野地址 - 报
runtime error: signed integer overflow？大概率是dist[u] + w溢出，加个if (dist[u] != LLONG_MAX)再算
