floyd 算法
template <typename T>
struct Floyd {
const T INF = std::is_same_v<T, long long> ? 1e18 : 1e9;
int n;
std::vector<std::vector<T>> dp;
Floyd(int n_) : n(n_) {
dp.resize(n + 1);
for (auto& row : dp) {
row.resize(n + 1, INF);
}
for (int i = 1; i <= n; i++) {
dp[i][i] = 0;
}
}
void calFloyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = std::min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
}
std::vector<std::vector<T>>& getDp() { return dp; }
};