CaixeiroViajante-C

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

#define inf 99999999

int dfs(int *pai, int **M, long long bitmask,int n,int last,int ret){
    int mn=inf;
    int i;
    for(i=0;i<n;i++){
        if(M[last][i]){
            if((bitmask&(1LL<<i))>0){
                int val=dfs(pai, M, bitmask-(1LL<<i),n,i,ret)+ M[last][i];
                if(mn>val){
                    mn = val;
                    pai[last]=i;
                }
            }
        }
    }
    if(bitmask==0){
        pai[last]=ret;
        return M[last][ret];
    }
    return mn;
}

int main(){
    int n,i,j;
    scanf("%d", &n);
    int **M = malloc(n * sizeof(int *));
    int *pai = malloc(n* sizeof(int));
    for(i = 0; i < n; i++)
        M[i] = malloc(n * sizeof(int));

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d", &M[i][j]);
//          if(M[i][j] == 0){
//              M[i][j] = inf;
//          }
        }
    }
    int bitmask = (1LL << n) - 1;
    int resp = inf;
    int id=0;
    int val;
    for(i=0;i<n;i++){
        val = dfs(pai, M, bitmask-(1LL<<i),n,i,i);
        if(resp > val){
            resp = val;
            id = i;
        }
    }
    dfs(pai, M, bitmask-(1LL<<id),n,id,id);
    i = id;
    printf("Caminho: %d ", id);
    i=pai[i];
    while (i != id){
        printf("-> %d ", i);
        i = pai[i];
    }
        printf("\nTamanho : %d\n", resp);

    return 0;
}