#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

int matriz[10][10];
int cAtual[11], cOriginal[11] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, }, cMenorCusto[11];
int n = 5, menorCusto;

void ler();

void imprimir(int vetor[11]);
void imprimirValorSoma(int soma);
void inverter(int inicio, int fim);
void copiar(int vetor1[11], int vetor2[11]);

void calcularHeuristica();
int calcularValor(int caminho[11]);
void validaCaminho(int caminho[11]);

int main() {
  srand(time(NULL));

  ler();

  calcularHeuristica();

  printf("\n\nMenor custo possivel: %d", menorCusto);
  imprimir(cMenorCusto);

  return 0;
}

int calcularValor(int caminho[11]) {
	int soma = 0, i;

	for(i = 0; i < n - 1; i++) {
		if(matriz[caminho[i]][caminho[i + 1]] != 0) {
			soma += matriz[caminho[i]][caminho[i + 1]];
			//printf("\nmatriz[%d][%d]: %d", caminho[i], caminho[i+1], matriz[caminho[i]][caminho[i + 1]]);
		} else {
			soma = 0;
			break;
		}

	}

	if(soma > 0) {
		if(matriz[caminho[i]][caminho[0]] != 0) {
			soma += matriz[caminho[i]][caminho[0]];
			if(soma < menorCusto) {
				menorCusto = soma;
				copiar(cMenorCusto, caminho);
			}
			//printf("\nmatriz[%d][%d]: %d", caminho[i], caminho[0], matriz[caminho[i]][caminho[0]]);
		} else {
			soma = 0;
		}
	}

	return soma;

}

void calcularHeuristica() {
	int j, i;
	for(j = 2; j < n; j++) {
		printf("\n\nFazendo troca entre %d\n", j);

		for(i = 1; i < n - j + 1; i++) {
			inverter(i, i + j - 1);
			imprimir(cAtual);
			imprimirValorSoma(calcularValor(cAtual));
		}
		getch();
	}
}

void imprimirValorSoma(int soma) {
	if(soma > 0) {
		printf(" = %d", soma);
	} else {
		printf(" = Alguma aresta eh vazia!");
	}
}

void inverter(int inicio, int qt) {
	int fim = inicio + qt + 1;
	int temp;

	copiar(cAtual, cOriginal);
	int contador;
	for (contador = inicio; contador < fim/2; ++contador){
		temp = cAtual[contador];
		cAtual[contador] = cAtual[fim - contador - 1];
		cAtual[fim - contador - 1] = temp;
   }
}

void copiar(int vetor1[11], int vetor2[11]) {
	int i;
	for(i = 0; i < n; i++) {
		vetor1[i] = vetor2[i];
	}
}

void imprimir(int vetor[11]) {
	printf("\n");
	int i;
	for(i = 0; i < n; i++) {
		printf("%d --> ", vetor[i]);
	}
	printf("%d", vetor[0]);
}

void imprimirMatriz() {
  int i, j;

  printf("\n     ");

  for(i = 0; i < n; i++) {
	printf("%2d ", i);
  }

  printf("\n-----");

  for(i = 0; i < n; i++) {
	printf("---");
  }

  printf("\n");

  for(i = 0; i < n; i++) {
  	printf("%2d | ", i);
  	for(j = 0; j < n; j++) {
  		printf("%2d ", matriz[i][j]);
	  }
	  printf("\n");
  }
}

void ler() {
	int i, j;

	n = (rand() % 7) + 3;

	printf("Numero de nodos = %d\n", n);

	for(i = 0; i < n; i++) {
		for(j = 0; j < n; j++) {
			matriz[i][j] = rand() % 10;
		}
	}

	for(i = 0; i < n; i++) {
		matriz[i][i] = 0;
	}

	imprimirMatriz();

	do {

		cOriginal[0] = rand() % n;

		for(i = 0; i < n; i++) {
			int x = rand() % n;

			for(j = 0; j < i; j++) {
				if(cOriginal[j] == x) {
					i--;
					break;
				} else {
					cOriginal[i] = x;
				}
			}
			//printf("\ncOriginal[%d] = %d", j, cOriginal[j]);
		}
  	} while(calcularValor(cOriginal) == 0);

  	imprimir(cOriginal);
	imprimirValorSoma(calcularValor(cOriginal));

	copiar(cMenorCusto, cOriginal);
	menorCusto = calcularValor(cOriginal);

}