#include <iostream>
#include <vector>
#include <Windows.h>
using namespace std;

using double_vector_t = vector<vector<int>>;
using coordinate_t = pair<int, int>;
using coordinate_with_flag_t = pair<coordinate_t, bool>;

bool isChangedMaxWayLength = false;

//done
void print(vector<coordinate_t>& resultWay)
{
	cout << "Result way:" << endl;
	for (int j = 0; j < resultWay.size(); j++)
	{
		cout << "(" << resultWay[j].first << ":" << resultWay[j].second << ")" << ", ";
	}
}

// done
int getCrossAmount(double_vector_t& matrix, const int& N, const int& node)
{
	int amount = 0;
	for (int j = 0; j < N; j++)
	{
		if (matrix[node][j] != 0)
		{
			amount++;
		}
	}
	return amount;
}

// done
int getMaxWayLength(double_vector_t& matrix, const int& N)
{
	int summary = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (matrix[i][j] != 0)
			{
				summary += matrix[i][j];
			}
		}
	}
	int response;
	for (int i = 0; i < N; i++)
	{
		response = getCrossAmount(matrix, N, i);
		if (response != 0)
		{
			summary += pow(response, response);
		}
	}
	return summary;
}

// done
int isAlreadyVisited(vector<coordinate_with_flag_t>& visited, const coordinate_t& node)
{
	for (int k = 0; k < visited.size(); k++)
	{
		if (visited[k].first.first == node.first && visited[k].first.second == node.second ||
			visited[k].first.second == node.first && visited[k].first.first == node.second)
		{
			return visited[k].second == true;
		}
	}
	return false;
}


// done
void markVisited(vector<coordinate_with_flag_t>& visited, const coordinate_t& node)
{
	const int visitedSize = visited.size();
	for (int k = 0; k < visitedSize; k++)
	{
		if (visited[k].first.first == node.first && visited[k].first.second == node.second ||
			visited[k].first.second == node.first && visited[k].first.first == node.second)
		{
			visited[k].second = true;
		}
	}
}

//done
void markUnvisited(vector<coordinate_with_flag_t>& visited, const coordinate_t& node)
{
	for (int k = 0; k < visited.size(); k++)
	{
		if (visited[k].first.first == node.first && visited[k].first.second == node.second ||
			visited[k].first.second == node.first && visited[k].first.first == node.second)
		{
			visited[k].second = false;
		}
	}
}

// done
bool isAllVisited(vector<coordinate_with_flag_t>& visited)
{
	for (int i = 0; i < visited.size(); i++)
	{
		if (visited[i].second == false)
		{
			return false;
		}
	}
	return true;
}

void getOptimizedWay(double_vector_t& matrix,
                     int& maxWayLength,
                     int& wayLength,
                     vector<coordinate_t>& currentWay,
                     vector<coordinate_t>& resultWay,
                     vector<coordinate_with_flag_t>& visited,
                     const int& i)
{
	currentWay.push_back(coordinate_t(i, 0));
	for (int j = 0; j < matrix.size(); j++)
	{
		coordinate_t currentNode(i, j);

		if (matrix[i][j] != 0 && !isAlreadyVisited(visited, currentNode) && wayLength + matrix[i][j] < maxWayLength)
		{
			wayLength += matrix[i][j];
			markVisited(visited, currentNode);
			if (isAllVisited(visited))
			{
				if (isChangedMaxWayLength == false || wayLength < maxWayLength)
				{
					currentWay.push_back(coordinate_t(i, j));

					isChangedMaxWayLength = true;
					resultWay = currentWay;
					maxWayLength = wayLength;

					currentWay.pop_back();
				}
			}
			else
			{
				getOptimizedWay(matrix, maxWayLength, wayLength, currentWay, resultWay, visited, j);
			}
			wayLength -= matrix[i][j];
			markUnvisited(visited, currentNode);
		}
	}
	currentWay.pop_back();
}


int main()
{
	SetConsoleCP(1251);
	SetConsoleOutputCP(1251);

	double_vector_t matrix
	{
		{0, 10, 20},
		{10, 0, 0},
		{20, 0, 0}
	};

	int N = matrix.size();
	int wayLength = 0, maxWayLength = getMaxWayLength(matrix, N);
	vector<coordinate_with_flag_t> visited;
	vector<coordinate_t> currentWay, resultWay;

	cout << "Наши данные: " << endl;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << matrix[i][j] << " ";
		}
		cout << endl;
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (matrix[i][j] != 0)
			{
				visited.push_back(coordinate_with_flag_t(coordinate_t(i, j), false));
			}
		}
	}

	for (int i = 0; i < N; i++)
	{
		coordinate_t currentNode(i, 0);
		visited.push_back(coordinate_with_flag_t(currentNode, true));
		visited.push_back(coordinate_with_flag_t(coordinate_t(0, i), true));
		getOptimizedWay(matrix, maxWayLength, wayLength, currentWay, resultWay, visited, i);
		visited.pop_back();
		visited.pop_back();
	}

	cout << endl << "Length: " << maxWayLength << endl;
	print(resultWay);
}