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

int matriz[10][10], visitado[10], n, custo=0;

void ler();
void imprimir();
int minimo(int c);
void custoMinimo(int cidade);

void main() {
  system("cls");

  ler();

  printf("\n\nO caminho eh: \n\n");

  custoMinimo(0);

  imprimir();

  getch();
}

void custoMinimo(int cidade) {
  int i, nCidade;

  visitado[cidade] = 1;

  printf("%d -->", cidade + 1);
  nCidade = minimo(cidade);

  if(nCidade == 999) {
    nCidade = 0;
    printf("%d", nCidade+1);
    custo += matriz[cidade][nCidade];
    return;
  }

  custoMinimo(nCidade);

}

int minimo(int c) {
  int i, nC = 999;
  int minimo = 999, kMinimo;

  for(i = 0; i < n; i++) {
    if((matriz[c][i] != 0) && (visitado[i] == 0))
      if(matriz[c][i] + matriz[i][c] < minimo) {
        minimo = matriz[i][c]; //+matriz[c][i];
        kMinimo = matriz[c][i];
        nC = i;
      }
  }

  if(minimo != 999)
    custo += kMinimo;

  return nC;

}

void imprimir() {

  printf("\n\nMinimum custo:");
  printf("%d", custo);

}

void ler() {
  int i, j;

  printf("Informe o numero de cidades: ");
  scanf("%d", &n);
  printf("\nInforme o custo da matriz\n");

  for(i = 0; i < n; i++) {
    printf("\nInforme os elementos da linha # : %d\n", i+1);
    for(j = 0; j < n; j++)
      scanf("%d", &matriz[i][j]);
    visitado[i] = 0;
  }

  printf("\n\nO custo da lista eh:\n\n");
  for( i=0;i < n;i++) {
    printf("\n\n");
    for(j = 0; j < n; j++)
      printf("\t%d", matriz[i][j]);
  }
}