千万级稠密图下的多色点对最短路优化方案

——为什么 PQ-SPFA（Dijkstra 变体）在高性能架构下能实现百倍超越？

一、算法原理：二进制分组与最短路引擎

为了让博客完整，我们先简单复述一下如何解决“任意异色点对最短路”这个问题。

1. 二进制分组：降维的艺术 既然是找异色点对，我们利用一个显然的性质：颜色 $A$ 和颜色 $B$ 不同，它们的二进制表示中至少有一位不同。因此，我们可以枚举二进制的第 $k \in [0, \lceil \log_2 C \rceil]$ 位，把全图节点分成“第 $k$ 位为 0”和“第 $k$ 位为 1”两个集合，相互跑多源最短路。这样就把 $O(N^2)$ 的枚举，降维成了 $\log_2 C$ 次单源最短路。

2. 核心引擎的抉择 接下来就是本文的重头戏：底层的最短路引擎到底用什么？

传统方案 SPFA (SLF)：依靠 deque 维护待更新的节点。在稠密图中，一旦加入负权，它极易产生“震荡效应”。同一个节点可能被反复推入队列成千上万次，毫无下限地榨干 CPU。
The Hero：PQ-SPFA：引入 priority_queue。这其实是带了“反悔机制”的 Dijkstra。虽然它保留了 SPFA 允许节点多次入队处理负权边的特性，但它强迫算法在每一次扩展时，都必须处理当前全局的最优点。这个小小的限制，从根本上砍掉了 99% 的无效松弛。

二、深度复盘：为什么 SLF-SPFA 彻底崩了？

为什么同样是跑图，SLF 会慢得如此离谱，以至于到达了380秒这样的成绩？

1. 松弛风暴（Relaxation Storm） 在 $M = 10^7$ 的稠密图中，每个节点的平均出度高达 200。想象一下，当队列中弹出一个次优的节点，它会立刻更新它的 200 个邻居，这 200 个邻居又会被推进队列。紧接着，一个微小的负权更新传导过来，刚刚那 200 个邻居全算错了，必须重新排队再算一遍！这就是松弛风暴。几轮震荡下来，CPU 的指令周期全在无效空转。

2. SLF 的局限性：局部最优 vs 全局最优 SLF 优化的逻辑是：“如果新入队的节点距离小于队首，就插到队头”。这只是一个局部的短视操作。在极端复杂的千万级大图里，它根本无法建立起一个宏观的、全局的最优拓展顺序。

3. 内存吞吐的致命伤：Cache Miss SLF 依赖 std::deque。在 C++ 底层，deque 是由一段段不连续的内存块拼接而成的。当吞吐量达到千万级别时，这种非连续的内存跳转会引发疯狂的 Cache Miss（缓存未命中），内存访问延迟被无限放大，最终拖垮整个系统。

三、硬件视角：Apple M1 芯片的助攻

11.2 秒处理千万级别边（还要跑十几次），光靠算法是不够的，这里面有着现代芯片微架构的巨大红利。

1. 分支预测（Branch Prediction）的奇迹 很多人不敢用 priority_queue，是怕堆的 Up/Down 调整带来的 $O(\log V)$ 复杂度。但现代 CPU，尤其是 Apple M1 这种拥有恐怖乱序执行和分支预测单元的芯片，对高度规律的内存访问有着极强的亲和力。M1 的分支预测器几乎完美预判了堆调整的路径，使得这部分指令的耗时在流水线中变得近乎“透明”。

2. UMA（统一内存架构）与硬件预取 M1 的 UMA 架构拥有夸张的内存带宽。我在代码中大量使用了 std::vector。无论是邻接表还是 priority_queue，底层全都是绝对连续的线性内存。当 CPU 顺序读取 vector 时，触发了完美的硬件预取（Hardware Prefetching），数据在你需要之前就已经被提前塞进了 L1 Cache。这就是 11 秒奇迹的物理基础。

四、源码公开 (The Code)

下面放出我最终压榨出 11 秒成绩的完整源码。特别注意以下三个极致压缩常数的核心点：

快读 (read())：面对几千万个整数的输入输出，抛弃 cin，直接操作字符流，榨干 I/O 时间。
priority_queue 类型选择：严格使用 greater<> 构造小根堆。
in_q 的反悔位置：出队时置为 false，入队时置为 true。绝不漏掉负权边引发的任何一次更优更新。

cpp

// 千万级稠密图多色点对最短路
// Binary Grouping + PQ-SPFA Optimization

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const long long INF = 1e18;
const int MAXN = 200005;

struct Edge {
    int to;
    int weight;
};

vector<Edge> adj[MAXN];
int color[MAXN];
long long dist_arr[MAXN];
bool in_q[MAXN];

// 竞赛级快读：极限压榨 I/O 时间
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

// 核心最短路引擎：PQ-SPFA (带优先队列修正的标签修正算法)
long long standard_sequential_spfa(const vector<int>& sources, const vector<int>& targets, int n) {
    for (int i = 0; i <= n; ++i) {
        dist_arr[i] = INF;
        in_q[i] = false;
    }

    // 强迫症级别的全局最优引导
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;

    for (int s : sources) {
        dist_arr[s] = 0;
        pq.push({0, s});
        in_q[s] = true;
    }

    while (!pq.empty()) {
        // --- 核心改动：不再盲目取队首，直接处理堆顶（当前全局最近点） ---
        int u = pq.top().second;
        pq.pop();

        // 出队解除标记，拥抱负权边带来的“反悔”可能
        in_q[u] = false;

        for (auto& edge : adj[u]) {
            int v = edge.to;
            if (dist_arr[u] + edge.weight < dist_arr[v]) {
                dist_arr[v] = dist_arr[u] + edge.weight;
                // 如果当前节点不在队列中，将其入队
                if (!in_q[v]) {
                    pq.push({dist_arr[v], v});
                    in_q[v] = true;
                }
            }
        }
    }

    long long min_dist = INF;
    for (int t : targets) {
        if (dist_arr[t] < min_dist) min_dist = dist_arr[t];
    }
    return min_dist;
}

void solve() {
    int n = read(), m = read();
    int max_color = 0;

    for (int i = 1; i <= n; ++i) {
        color[i] = read();
        if (color[i] > max_color) max_color = color[i];
    }

    // 千万级边构建
    for (int i = 0; i < m; ++i) {
        int u = read(), v = read(), w = read();
        if (u >= 1 && u <= n) adj[u].push_back({v, w});
    }

    long long final_ans = INF;

    // 二进制分组逻辑：复杂度 O(log C * E log V)
    for (int k = 0; (1ll << k) <= max_color; ++k) {
        vector<int> g0, g1;
        for (int i = 1; i <= n; ++i) {
            if ((color[i] >> k) & 1) g1.push_back(i);
            else g0.push_back(i);
        }
        if (g0.empty() || g1.empty()) continue;

        // 正反向松弛
        final_ans = min(final_ans, standard_sequential_spfa(g0, g1, n));
        final_ans = min(final_ans, standard_sequential_spfa(g1, g0, n));
    }
    if (final_ans == INF) {
        cout << -1 << endl;
    } else {
        cout << final_ans << endl;
    }

}

int main() {

    solve();

}

千万级稠密图下的多色点对最短路优化方案 ​

——为什么 PQ-SPFA（Dijkstra 变体）在高性能架构下能实现百倍超越？ ​

一、 算法原理：二进制分组与最短路引擎 ​

二、 深度复盘：为什么 SLF-SPFA 彻底崩了？ ​

三、 硬件视角：Apple M1 芯片的助攻 ​

四、 源码公开 (The Code) ​