caxeiro

#include <iostream>
#include <string.h>

using namespace std;

int solve(int, long);

const int NOT_SOLVED = -1;
const int MAX_INT = ~(1 << 31);

int nVertices;
long allVisited;
int** distances;
int** solved;

int nReachedSolutionEnd = 0;
int nSolvedAttribution = 0;
int nSolvedUsed = 0;

int main()
{
	cin >> nVertices;

	if (nVertices > 65)
	{
		cout << "This algorithm can not solve this problem." << endl;
		cout << "The number of vertices, " << nVertices << ", is too hight!" << endl;
		cout << "The supported number of vertices is 65." << endl;
		return 1;
	}

	allVisited = (1 << (nVertices - 1)) - 1;

	distances = new int*[nVertices];
	solved = new int*[nVertices];

	long solvedSize = allVisited - 1;

	cout << "nVertices " << nVertices << endl;
	cout << "solvedSize " << solvedSize << endl;

	cout << "allVisited ";
	for (int i = nVertices - 2; i >= 0; i--)
		cout << ((allVisited & (1 << i)) ? 1 : 0);
	cout << " (" << allVisited << ")" << endl;

	for (int row = 0; row < nVertices; row++)
	{
		distances[row] = new int[nVertices];

		for (int col = 0; col < nVertices; col++)
			cin >> distances[row][col];

		solved[row] = new int[solvedSize];
		memset(solved[row], NOT_SOLVED, solvedSize * sizeof(int));
	}

	cout << solve(0, 0) << endl;
	cout << "Reached solution end " << nReachedSolutionEnd << " times." << endl;
	cout << "Solved array alements were attributed " << nSolvedAttribution << " times." << endl;
	cout << "Used solved values " << nSolvedUsed << " times." << endl;

	return 0;
}

int solve(int from, long visited)
{
	if (visited == allVisited)
	{
		nReachedSolutionEnd++;
		return distances[from][0];
	}

	if (solved[from][visited] != NOT_SOLVED)
	{
		nSolvedUsed++;
		return solved[from][visited];
	}

	cout << "At " << from << ", visited ";
	for (int i = nVertices - 2; i >= 0; i--)
		cout << ((visited & (1 << i)) ? 1 : 0);
	cout << " (" << visited << ")" << endl;

	int shortest = MAX_INT;

	for (int i = 1; i < nVertices; i++) {
		int vertice = 1L << (i - 1);

		if (!(visited & vertice))
		{
			int distance = distances[from][i] + solve(i, visited | vertice);
			if (distance < shortest) shortest = distance;
		}
	}

	nSolvedAttribution++;
	return solved[from][visited] = shortest;
}