全点対最短経路(ワーシャルフロイド法)
(graph/warshall-floyd.hpp)

• View this file on GitHub
• Last update: 2022-12-30 04:45:51+09:00
• Include: #include "graph/warshall-floyd.hpp"
• Link: View error logs on GitHub Actions

Verified with

• verify/AOJ-GRL_1_C.test.cpp

Code

template<typename T>
vector<vector<T>> warshallFloyd(vector<vector<T>> mat, T infty){
  int n = mat.size();
  for(int k = 0; k < n; ++k){
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < n; ++j){
        if(mat[i][k] == infty || mat[k][j] == infty) continue;
        mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
      }
    }
  }
  return mat;
}

#line 1 "graph/warshall-floyd.hpp"
template<typename T>
vector<vector<T>> warshallFloyd(vector<vector<T>> mat, T infty){
  int n = mat.size();
  for(int k = 0; k < n; ++k){
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < n; ++j){
        if(mat[i][k] == infty || mat[k][j] == infty) continue;
        mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
      }
    }
  }
  return mat;
}

Back to top page