// 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;
}