#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <locale>

using namespace std;

class Task
{
public:
	int n, m;
	int x, y, w;
	int **Graph;
	int Initial_Vertex, Max;
	int *Way;
	int **Span;
	int Sum;

public: Task(){};

public: void ReadData(char *s)
{
	ifstream f;
	f.open(s);
	if (f.fail()) cout << "Ошибка чтения файла" << endl;
	f >> n;
	Graph = new int*[n];
	for (int i = 0; i < n; i++)
	{
		Graph[i] = new int[n];
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			Graph[i][j] = 0;
		}
	}
	f >> m;
	for (int i = 0; i < m; i++)
	{
		f >> x >> y >> w;
		Graph[x][y] = w;
		Graph[y][x] = Graph[x][y];
	}
	f >> Max;
	cout << "Матрица смежности графа" << endl;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << Graph[i][j] << " ";
			if (Graph[i][j] == 0) Graph[i][j] = Max;
		}
		cout << "\n";
	}
	f >> Initial_Vertex;
	f.close();
}
public: void WriteData(char *s, int **Span, int *Way, int Sum)
{
	ofstream f;
	f.open(s);
	if (f.fail()) cout << "Ошибка записи файла" << endl;
	f << n << endl;
	f << n - 1 << endl;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (Span[i][j] != 0 && i < j)
				f << i << " " << j << " " << Span[i][j] << endl;
		}
	for (int i = 0; i < n; i++)
		f << Way[i] << endl;
	f << Sum;
	f.close();
}
};

class AlgorithmPrima
{
public:
	Task data;
	int Count;
	int Min;
	int x, y;
	bool *Visited;

public:	 AlgorithmPrima(){};

public: void Algorithm()
{
	data.ReadData("D:\\Prima\\input.txt");
	MST(data.n, data.Graph, data.Initial_Vertex, data.Max);
	data.WriteData("D:\\Prima\\output.txt", data.Span, data.Way, data.Sum);
}

void MST(int n, int **Graph, int Vertex, int Max)
{
	Visited = new bool[n];
	for (int i = 0; i < n; i++)
		Visited[i] = false;
	data.Way = new int[n];
	for (int i = 0; i < n; i++)
		data.Way[n] = 0;
	data.Span = new int*[n];
	for (int i = 0; i < n; i++)
		data.Span[i] = new int[n];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			data.Span[i][j] = 0;
	time_t start = time(NULL);
	Count = 0;
	data.Sum = 0;
	Visited[Vertex] = true;
	data.Way[0] = Vertex;
	while (Count < n - 1)
	{
		Min = Max;
		for (int k = 0; k <= Count; k++)
			for (int j = 0; j < n; j++)
				if ((Graph[data.Way[k]][j] < Min) && (Visited[j] == false))
				{
					Min = Graph[data.Way[k]][j];
					y = data.Way[k];
					x = j;
				}
		Count = Count + 1;
		data.Way[Count] = x;
		Visited[x] = true;
		Graph[x][y] = 0;
		data.Span[x][y] = Min;
		Graph[y][x] = 0;
		data.Span[y][x] = Min;
		data.Sum = data.Sum + Min;
	}
	time_t finish = time(NULL);
	Print(n, data.Span, data.Way, data.Sum, finish-start);
}

void Print(int n, int **Span, int *Way, int Sum, time_t Time)
{
	cout << "\nМатрица смежности остова\n";
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << Span[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\nМаршрут: ";
	for (int i = 0; i < n; i++)
	{
		cout << Way[i];
		if (i < n - 1) cout << " --> ";
	}
	cout << endl;
	cout << "\nМинимальная стоимость пути: " << Sum << endl;
	cout << "\nВремя выполнения алгоритма: " << Time << " сек. " << endl;
}
};

int _tmain(int argc, _TCHAR* argv[])
{
	setlocale(LC_ALL, "RUS");
	AlgorithmPrima a;
	a.Algorithm();
	system("pause");
	return 0;
}