//
//  main.cpp
//  vaja5warshall
//
//  Created by Nejc Drobnic on 21/05/2019.
//  Copyright © 2019 Nejc Drobnic. All rights reserved.
//

#include <iostream>
#include <fstream>

using namespace std;

int stPov = 0, vel = 0;

int D[30][30];
int C[30][30];
int H[30][30];

void beri(string f)
{
    fstream dat(f.c_str(), fstream::in);
    dat >> vel;
    int i=0;
    int p, q, c;

    while(!dat.eof())
    {
        dat >> p >> q >> c;
        C[q-1][p-1] = c;
        i++;
    }
    dat.close();
}
//C - matrika sosednosti
//D - matrika najkrajših poti
//H - matrika predhodnikov
void FLOYD_WARSHALL()
{
    for(int i = 0; i < vel; i++)
    {
        for(int j = 0; j < vel; j++)
        {
            D[i][j] = C[i][j];
            if(i != j && C[i][j] != 1000000)
            {
                H[i][j] = i + 1;
            }
            else
            {
                H[i][j] = -1;//-1 ker null ne sprejme int
            }
        }
    }
    for(int k = 0; k < vel; k++)
    {
        for(int i = 0; i < vel; i++)
        {
            for(int j = 0; j < vel; j++)
            {
                if(D[i][j] > D[i][k] + D[k][j])
                {
                    D[i][j] = D[i][k] + D[k][j];
                    H[i][j] = H[k][j];
                }
            }
        }
    }
}

void IZPIS_POTI(int s, int g)
{
    if(s == g)
    {
        cout << s << endl;
    }
    else if(H[s - 1][g - 1] == -1)
    {
        cout << "med s in g ni poti" << endl;
    }
    else
    {
        IZPIS_POTI(s, H[s - 1][g - 1]);
        cout << g << endl;
    }
}


int main(int argc, const char * argv[])
{
    int start, end = 0;
    beri("graf.txt");
    for(int i = 0; i < vel; i++)
    {
        for(int j = 0; j < vel; j++)
        {
            cout << C[i][j] << " ";
        }
        cout << endl;
    }

    FLOYD_WARSHALL();
    cout << "Algoritem zagnan" << endl;

    cout << "zacetno vozlisce: ";
    cin >> start;

    cout << "koncno vozlice: ";
    cin >> end;

    IZPIS_POTI(start, end);
    return 0;
}