思路与算法

需要所有有序点对的距离，因此使用Floyd。距离矩阵初始化：对角线0，其余F=10^16；逐边用min处理重边。最外层枚举中间点k，对可达的i→k、k→j执行d[i][j]=min(d[i][j],d[i][k]+d[k][j])。最后初始化S=0，对全部n²个点对异或d[i][j]+F。

正确性说明

设D_k(i,j)只允许1..k作内部顶点的最短路。初始矩阵恰好是无内部顶点的空路或直接边；重边取最小。最优路径若不用k，费用为D_(k−1)(i,j)；若用k，在无负环条件下可以去掉非负回路，选一条不重复k的最短路，分成i→k和k→j两段。取两种情况最小即递推式，按k归纳最后得到全对距离。原地更新安全，因为无负环使d[k][k]=0，本轮的第k行列不会因经过k而改善。F只表示不可达，跳过任何含F的两段，防止负边把无路错误变成有限距离。最终对每个有序点对各执行一次定义的异或，S初值0，故输出恰为目标。

复杂度

初始化O(n²+m)时间、距离矩阵O(n²)空间；Floyd O(n³)时间，最终聚合O(n²)。总时间O(n³+m)，额外空间O(n²)，无需保存全部边。无负环最短路可取至多n−1条边，有限距离绝对值不超过499×10^9，严格小于F；两有限距离相加和加F均远小于64位有符号整数上限。

易错点

k必须放最外层。不可达贡献是F+F=2F，不能跳过不可达点对；同一个无序点对的两个方向都要算，对角线也要算。S必须显式置0，不能使用未初始化局部变量；F应写成整数常量，避免把浮点字面量用于位运算。负权不代表负环，保证无负环时Floyd仍正确；重边取最小，自环和对角空路取最小。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m))
        return 0;
    const long long F = 10000000000000000LL;
    vector<vector<long long>> d(n, vector<long long>(n, F));
    for (int i = 0; i < n; i++)
        d[i][i] = 0;
    while (m--) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        --u;
        --v;
        d[u][v] = min(d[u][v], w);
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            if (d[i][k] != F)
                for (int j = 0; j < n; j++)
                    if (d[k][j] != F)
                        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    long long ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ans ^= d[i][j] + F;
    cout << ans << '\n';
}