#include <iostream>
#include <vector>
#include <limits>

#define INF (std::numeric_limits<int>::max())

typedef std::vector<std::vector<int>> Matrix;

void print_matrix(Matrix& mat)
{
    for (int i = 0; i < mat.size(); i++) {
        for (int j = 0; j < mat.size(); j++) {
            if (mat[i][j] == INF) {
                std::cout << "inf ";
            } else {
                std::cout << mat[i][j] << " ";
            }
        }
        std::cout << std::endl;
    }
}

void transitive_closure(Matrix& W, Matrix& T) 
{
    int n = W.size();

    T.resize(n);
    for (int i = 0; i < n; i++) {
        T[i].resize(n, 0);
        for (int j = 0; j < n; j++) {
            if (i == j || W[i][j] < INF) {
                T[i][j] = 1;
            } // else i != j && W[i][j] = inf: T[i][j] = 0;
        }
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                T[i][j] = T[i][j] || (T[i][k] && T[k][j]);
            }
        }
   }
}

int main(void)
{
    Matrix W = {
        {0, 3, 8, INF, -4},
        {INF, 0, INF, 1, 7},
        {INF, 4, 0, INF, INF},
        {2, INF, -5, 0, INF},
        {INF, INF, INF, 6, 0}
    };

    const int n = W.size();

    Matrix T;

    transitive_closure(W, T);

    print_matrix(T);
    
    return 0;
}