多源汇最短路（APSP问题）

使用邻接矩阵存图，可以处理负权边，以$O(N^3)$的复杂度计算。注意，这里建立的是单向边，计算 双向边需要额外加边。

using ll = long long;
constexpr ll INF = 4e18; // 防止相加溢出

// 预处理要求：
// 1. 初始化 d[i][j] = INF, d[i][i] = 0
// 2. 读入边权：d[u][v] = min(d[u][v], w)
auto floyd = [&](int n, vector<vector<ll>>& d) -> void {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            if (d[i][k] > INF / 2) continue; // 剪枝 & 防溢出
            for (int j = 1; j <= n; ++j) {
                if (d[k][j] < INF / 2) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }
};