#include <iostream>
#include <fstream>
#include <string>

using namespace std;

struct dijk_elem
{
    int dist;
    unsigned int pred;
};

void lire_graphe(const string& fichier, int** mat_loc, unsigned int* mat_taille)
{
    unsigned int nb_sommets;
    unsigned int nb_arcs;
    ifstream source_graphe(fichier.c_str());

    source_graphe >> nb_sommets;
    cout << "Nombre de sommets : " << nb_sommets << "\n";
    source_graphe >> nb_arcs;
    cout << "Nombre d'arcs : " << nb_arcs << "\n";

    int* mat_inc = new int[nb_sommets * nb_sommets];

    for (unsigned int i(0); i < nb_sommets; ++i)
        for (unsigned int j(0); j < nb_sommets; ++j)
            mat_inc[i + j * nb_sommets] = static_cast<unsigned int>(-1);

    for (unsigned int i(0); i < nb_arcs; ++i)
    {
        unsigned int sommet_initial;
        unsigned int sommet_final;
        source_graphe >> sommet_initial;
        source_graphe >> sommet_final;
        source_graphe >> mat_inc[sommet_initial + sommet_final * nb_sommets];
    }

    *mat_loc = mat_inc;
    *mat_taille = nb_sommets;
}

void affiche_etat(dijk_elem* table, unsigned int mat_taille, int sommet_courant)
{
    cout.width(5);
    if(sommet_courant == -1)
        cout << "        ";
    else
        cout << sommet_courant << " : ";

    for(int i = 0 ; i < mat_taille ; i++)
    {
        cout.width(4);
        if(table[i].dist == -1)
        {
            cout << " ###, ### |";
            continue;
        }

        cout << table[i].dist;
        cout.width();
        cout << ",";
        cout.width(4);
        cout << table[i].pred;
        cout << " |";
    }

    cout << endl;
}

void affiche_chemin(dijk_elem* table, unsigned int courant, unsigned initial)
{
    if (courant == initial)
        cout << initial;
    else
    {
        affiche_chemin(table, table[courant].pred, initial);
        cout << " - " << courant;
    }
}

int main() {
    int *mat_inc;
    unsigned int mat_taille;
    string fichier;
    unsigned int sommet_initial;
    unsigned int sommet_courant;
    bool* MCC;
    dijk_elem* table;

    cout << "Entrez le nom du fichier : ";
    cin >> fichier;

    lire_graphe(fichier, &mat_inc, &mat_taille);
    MCC = new bool[mat_taille];
    table = new dijk_elem[mat_taille];
    for (unsigned int i(0); i < mat_taille; ++i)
    {
        MCC[i] = true;
        table[i].dist = -1;
        table[i].pred = 0;
    }

    cout << "Entrez le numéro du sommet initial (<" << mat_taille << ") : ";
    cin >> sommet_initial;

    table[sommet_initial].dist = 0;
    table[sommet_initial].pred = sommet_initial;
    sommet_courant = sommet_initial;

    cout << "\n  ";
    for (unsigned int i(0); i < mat_taille; ++i)
    {
        cout.width(10);
        cout << i << " ";
    }
    cout << '\n';

    affiche_etat(table, mat_taille, -1);

    for (unsigned int i(0); i < mat_taille; ++i)
    {
        MCC[sommet_courant] = false;
        for (unsigned int j(0); j < mat_taille; ++j)
            if (mat_inc[sommet_courant + j * mat_taille] >= 0 &&
                (table[j].dist == -1 ||
                 table[sommet_courant].dist + mat_inc[sommet_courant + j * mat_taille] < table[j].dist))
            {
                table[j].dist = table[sommet_courant].dist + mat_inc[sommet_courant + j * mat_taille];
                table[j].pred = sommet_courant;
            }
        affiche_etat(table, mat_taille, sommet_courant);
        unsigned int prochain_sommet;
        int dist = -1;
        for (unsigned int j(0); j < mat_taille; ++j)
            if (MCC[j] && table[j].dist != -1 && (dist == -1 || table[j].dist < dist))
            {
                prochain_sommet = j;
                dist = table[j].dist;
            }

        if (dist >= 0)
            sommet_courant = prochain_sommet;
    }

    affiche_etat(table, mat_taille, -1);

    cout << "\nPlus courts chemins : longueur\n";
    for (unsigned int i(0); i < mat_taille; ++i)
    {
        if (table[i].dist == -1)
            cout << i << " : Pas de chemin.\n";
        else
        {
            affiche_chemin(table, i, sommet_initial);
            cout << " : " << table[i].dist << '\n';
        }
    }

    delete[] mat_inc;
    delete[] MCC;
    delete[] table;

    return 0;
}