// AlgorytmDijkstry.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <string>
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <Windows.h>
#define const int MAXINT = 2147483647;


using namespace std;
struct slistEl
{
    slistEl * next;
    int start, weight;
};



void changecolor(int number_color) // Funkcja do zmienia koloru czcionki w consoli. Function to changing color of font in comand window.
{
    HANDLE handle;
    handle = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(handle, number_color);
}

int main()
{
    int i, j, howEdge,nodes, start, u, weight, index, edge, stos_index, *cost, *visited, *calculeted;
    bool *QS;
    slistEl **graf;
    slistEl *sasiad, *backup;
    ifstream plik;
    plik.open("graph.txt");
    plik >> start >> nodes >> howEdge;
    cost = new int[nodes];
    visited = new int[nodes];
    QS = new bool[nodes];
    graf = new slistEl *[nodes];
    calculeted = new int[nodes];
    stos_index = 0;
    for (i = 0; i < nodes; i++)
    {
        cost[i] = MAXINT;
        visited[i] = -1;
        QS[i] = false;
        graf[i] = NULL;
    }
    for (i = 0; i < howEdge; i++)
    {
        plik >> index >> edge >> weight;
        sasiad = new slistEl;
        sasiad->start = edge;
        sasiad->weight = weight;
        sasiad->next = graf[index];
        graf[index] = sasiad;
    }
    cost[start] = 0;
    for (i = 0; i < nodes; i++)
    {

        for (j = 0; QS[j]; j++);
        for (u = j++; j < nodes; j++)
            if (!QS[j] && (cost[j] < cost[u])) u = j;
        QS[u] = true;
        for (sasiad = graf[u]; sasiad; sasiad = sasiad->next)
            if (!QS[sasiad->start] && (cost[sasiad->start] > cost[u] + sasiad->weight))
            {
                cost[sasiad->start] = cost[u] + sasiad->weight;
                visited[sasiad->start] = u;
            }
    }
    cout << "Wierzcholek startowy to: ";
    changecolor(4);
    cout << start << endl;;
    changecolor(7);
    for (i = 0; i < nodes; i++)
    {
        if (i == start);
        else {

            cout << " Droga do wierzcholka ";
            changecolor(4);
            cout << i;
            changecolor(7);
            cout << " wiedzie przez wierzcholki: ";
            changecolor(4);
            for (j = i; j > -1; j = visited[j]) calculeted[stos_index++] = j;
            while (stos_index) cout << calculeted[--stos_index] << " ";
            changecolor(7);
            if (cost[i] >= MAXINT - 200 || cost[i] <= -MAXINT - 200) {
                string buff = "NIE ZNALEZIONO DROGI";
                cout << "i kosztuje: " << buff << " $ " << endl;
            }
            else cout << "i kosztuje: " << cost[i] << " $ " << endl;

        }
    }
    plik.close();
    delete[] cost;
    delete[] visited;
    delete[] QS;
    delete[] calculeted;

    for (i = 0; i < nodes; i++)
    {
        sasiad = graf[i];
        while (sasiad)
        {
            backup = sasiad;
            sasiad = sasiad->next;
            delete backup;
        }
    }
    delete[] graf;

    getchar();
    getchar();
    return 0;
}