#include <iostream>
#include <conio.h>
#include <math.h>
#include <stdio.h>

#pragma hdrstop
using std::cout;
using std::cin;
using std::endl;
#define N 7

//---------------------------------------------------------------------------
void view(int L[N][N]);
void viewstr(char S[N][N]);
void kw(int L_1[N][N], int L_2[N][N],int L_N[N][N]);
void rwn(int L_1[N][N], int L_2[N][N]);
void press();
//---------------------------------------------------------------------------




#pragma argsused
int main(int argc, char* argv[])
{
	char s[] = "ABCDEFG";


	int L1[N][N] = {
		0,  15, 999,  15, 999, 999,  35,
		15,   0,  30,  20, 999, 999, 999,
		999,  30,   0,  20,  35, 999, 999,
		15, 999,  20,   0,  40,  10,  50,
		999, 999,  35,  40,   0,  20, 999,
		999, 999, 999, 999,  20,   0,  10,
		35, 999, 999,  50, 999,  10,   0
	};



	cout << endl << "Mat L1 - rasstoyaniy neposredstvennix svyazey" << endl << endl;
	view(L1); //press();

	int L2[N][N];
	for (int i = 0; i <= N-1; i++)
		for (int j = 0; j <= N-1; j++)
			L2[i][j] = 999;

	kw(L1, L2, L1);

	cout << endl << "Matrica L2" << endl << endl;
	view(L2); rwn(L1, L2); //press();

	int L3[N][N];
	for (int i = 0; i <= N-1; i++)
		for (int j = 0; j <= N-1; j++)
			L3[i][j] = 999;
	cout << endl << "Matrica L3" << endl << endl;
	kw(L2, L3, L1);

	view(L3); rwn(L2, L3); //press();

	int L4[N][N];
	for (int i = 0; i <= N-1; i++)
		for (int j = 0; j <= N-1; j++)
			L4[i][j] = 999;
	cout << endl << "Matrica L4" << endl << endl;
	kw(L3, L4, L1);
	view(L4); rwn(L3, L4); //press();


	int L5[N][N];
	for (int i = 0; i <= N - 1; i++)
		for (int j = 0; j <= N - 1; j++)
			L5[i][j] = 999;
	cout << endl << "Matrica L5" << endl << endl;
	kw(L4, L5, L1);
	view(L5); rwn(L4, L5); //press();











	int G[N][N];
	for (int i = 0; i <= N-1; i++)
		for (int j = 0; j <= N-1; j++)
			if (L1[i][j] == 0) G[i][j] = 999;
			else G[i][j] = L1[i][j];
			cout << endl << "Matrica G - dlin neposredstvennix svyazey" << endl << endl; //матрица длин непосредственных связей
			view(G); //press();


			int DELTA[N][N]; //матрица кратчайших путей
			char dis[N][N];
			for (int i = 0; i <= N-1; i++)
				for (int j = 0; j <= N-1; j++)
					DELTA[i][j] = 999;
			for (int i = 0; i <= N-1; i++)
				for (int j = 0; j <= N-1; j++)
					for (int k = 0; k <= N-1; k++)
					{
						if (DELTA[i][j]>(G[i][k] + L4[k][j]))
						{
							DELTA[i][j] = (G[i][k] + L4[k][j]);
							dis[i][j] = s[k];
						};
						if (DELTA[i][j]>999)
							DELTA[i][j] = 999;

					}
			cout << endl << "Matrica DELTA - kratchayshih putey" << endl << endl;
			view(DELTA); //press();
			cout << endl << "Dispersionnaya matrica" << endl << endl;
			viewstr(dis);


			cout << "\n" << endl << "Press any key to exit...";
			getch();
			return 0;
}



//---------------------------------------------------------------------------
void view(int L[N][N])
{
	char str[] = "ABCDEFG";

	cout << "   | A   B   C   D   E  F  G \n-------------------------------\n";

	for (int i = 0; i <= N-1; i++)

	{
		cout << " " << str[i] << " |";

		for (int j = 0; j <= N-1; j++)
			if (L[i][j] == 0)    cout << "  " << L[i][j] << " ";
			else if (L[i][j]<100) cout << " " << L[i][j] << " "; else cout << L[i][j] << " ";
			cout << endl;
	}
};

//---------------------------------------------------------------------------
void kw(int L_1[N][N], int L_2[N][N], int L_N[N][N])
{
	for (int i = 0; i <= N - 1; i++) {
		for (int j = 0; j <= N-1; j++) {
			for (int k = 0; k <= N - 1; k++) {
				if (L_2[i][j] > L_N[i][k] + L_1[k][j]) {

					L_2[i][j] = L_N[i][k] + L_1[k][j];
				}
			}
			if (L_2[i][j] > 999) {
				L_2[i][j] = 999;
			}
		}
	}
};

void rwn(int L_1[N][N], int L_2[N][N])
{
	int sum = 0;
	int max = N*N;
	for (int i = 0; i <= N - 1; i++)
		for (int j = 0; j <= N - 1; j++) {
			if (L_1[i][j] == L_2[i][j])
				sum++;
		}

			if (sum == max) {
				cout << " RAVNO" << endl;
				cout << endl << "Matrica D - distancionnay matrica" << endl << endl; // дистанционная матрица
				view(L_2); //press();

			}
			else
				cout << " NOT RAVNO" << endl;

};
//---------------------------------------------------------------------------
void press()
{
	cout << endl << "Press any key to continue..." << endl;
	getch();
};

//---------------------------------------------------------------------------
void viewstr(char S[N][N])
{
	char str[] = "ABCDEFG";

	cout << endl << "  |A B C D E F G \n-----------------\n";
	for (int i = 0; i <= N-1; i++)

	{
		cout << " " << str[i] << "|";

		for (int j = 0; j <= N-1; j++)
			cout << S[i][j] << " ";
		cout << endl;
	};
};