Graph/WarshallFloyd.hpp

• View this file on GitHub
• Last update: 2023-04-05 23:10:22+09:00
• Include: #include "Graph/WarshallFloyd.hpp"

Verified with

• test/yuki5764.test.cpp

Code

template<typename T>
vector<vector<T>> WarshallFloyd(vector<vector<T>> mat, T inf=1000000100){
    int n=(int)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]<inf and mat[k][j]<inf) mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);
    return mat;
}

#line 1 "Graph/WarshallFloyd.hpp"
template<typename T>
vector<vector<T>> WarshallFloyd(vector<vector<T>> mat, T inf=1000000100){
    int n=(int)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]<inf and mat[k][j]<inf) mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);
    return mat;
}

Back to top page