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; }
};