#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 floyd_warshall(Matrix& W, Matrix& D, Matrix& Pi) 
{
    int n = W.size();

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

    D = W;
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (D[i][k] != INF && D[k][j] != INF &&
                    D[i][j] > D[i][k] + D[k][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                    Pi[i][j] = Pi[k][j];
                } 
            }
        }
    }
}

bool print_path(Matrix& Pi, int i, int j)
{
    if (i == j) {
        std::cout << i << std::endl;
        return true;
    } else if (Pi[i][j] == -1) {
        std::cout << "Ne postoji" << std::endl;
        return false;
    } 

    if (print_path(Pi, i, Pi[i][j])) {
        std::cout << j << " ";
        return true;
    } else {
        return false;
    }
}

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 D;
    Matrix Pi;

    floyd_warshall(W, D, Pi);

    print_matrix(D);
    std::cout << std::endl;
    print_matrix(Pi);
    std::cout << "Najkraci put od 2 do 0 je tezine "<< D[2][0] << ": ";
    print_path(Pi, 2, 0);
    
    return 0;
}