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

#define VSIZE 6

int minimum(int* find_D, int cnt, int* min_ind ){
    int mini=find_D[0];
    for(int i=0; i<cnt; i++){
        if(mini>find_D[i]){
            mini=find_D[i];
            *min_ind=i;
        }
    }
    return mini;
}

void travel(int n, int W[VSIZE][VSIZE], int **P){
    int j, cnt;
    int *find_D = (int*)malloc(sizeof(int)*n);
    int *find_P = (int*)malloc(sizeof(int)*n);
    int set = 0;
    int minLength = 0;
    int min_ind = 0;
    int max = 1 << n;

    int **D;
    D = (int**)malloc(sizeof(int*)*n);
    for(int i=0; i<n; i++)
        D[i] = (int*)malloc(sizeof(int)*max);

    // 부분집합 만들기
    int** sub;
    sub = (int**)malloc(sizeof(int*)*n);
    for(int i=0; i<n; i++)
        sub[i] = (int*)malloc(sizeof(int)*max);

    int* num=(int*)malloc(sizeof(int)*n);
    for(int i=0; i<n; i++)
        num[i]=0;

    for(int i=1; i<max; i++){
        if(i%2==1)          continue;   // V1을 포함하는 경우
        int temp=i/2;
        int c=0;
        while(1){
            if(temp==0)     break;
            if(temp%2==1)   c++;
            temp = temp/2;
        }
        sub[c-1][num[c-1]]=i;
        num[c-1]++;
    }

    // A가 공집합인 경우
    for(int i = 1; i < n; i++ )
        D[i][0] = W[i][0];

    for(int k = 1; k <= n - 2; k++ ){   // k=집합 A에 포함되는 정점의 개수
        for(int l=0; l<num[k-1]; l++){
            set=sub[k-1][l];            // 부분집합 저장
            for(int i=1; i<n; i++ ){
                if( (set & (1<<i))>0 )  // 집합에 포함되는 Vi은 실행하지 않는다
                    continue;
                for(j=1, cnt=0; cnt<k; j++ ){
                    if( (set & (1<<j))>0 ){ // set의 원소 Vj
                        find_D[cnt] = W[i][j] + D[j][set^(1<<j)];
                        find_P[cnt] = j;
                        cnt++;
                    }
                }
                D[i][set] = minimum(find_D, cnt, &min_ind);
                P[i][set] = find_P[min_ind];
            }
        }
    }

    // V1을 제외한 모든 정점을 포함하는 집합
    set=(max-1)-1;

    for(int i=1, cnt=0; cnt<n-1; i++ ){
        if( (set & (1<<i)) > 0 ){
            find_D[cnt] = W[0][i] + D[i][set^(1<<i)];
            find_P[cnt] = i;
            cnt++;
        }
    }
    D[0][set] = minimum(find_D, cnt, &min_ind);
    P[0][set] = find_P[min_ind];
    minLength = D[0][set];


    //메모리해제
    free(find_D);
    free(find_P);
    free(num);
    for(int i=0; i<n; i++)
        free(sub[i]);
    free(sub);
    for(int i=0; i<n; i++)
        free(D[i]);
    free(D);
}

int main(){
    int W[VSIZE][VSIZE];
    int r1, r2;
    int n = VSIZE;
    int max = 1<<n;

    int **P=(int**)malloc(sizeof(int*)*n);
    for(int i=0; i<n; i++)
        P[i]=(int*)malloc(sizeof(int)*max);

    int M[VSIZE][VSIZE]={
        {   0,      556600, 595600, 933100, 781400, 2011700 },  // 한국
        {   719000, 0,      92426,  849764, 968538, 1562927 },  // 영국
        {   687477, 114695, 0,      743700, 1281868,1562927 },  // 스위스
        {   606631, 456119, 458768, 0,      648926, 2508514 },  // 남아공
        {   764054, 751741, 667857, 966518, 0,      842861  },  // 워싱턴
        {   1867523,1788451,1349493,1223562,1013584,0       }   //파라과이
    };
    int T[VSIZE][VSIZE]={
        {0,     2195,   975,    2470,   992,    1685},  // 한국
        {1650,  0,      100,    910,    660,    1540},  // 영국
        {995,   110,    0,      1085,   1568,   1540},  // 스위스
        {1200,  1145,   1430,   0,      2700,   2570},  // 남아공
        {995,   645,    1450,   2338,   0,      732},   // 워싱턴
        {2340,  1390,   2345,   3020,   1184,   0   }   //파라과이
    };

    while(1){
        printf("비용: ");
        scanf("%d", &r1);
        printf("시간: ");
        scanf("%d", &r2);
        if(r1+r2==100)
            break;
        printf("잘못된 값입니다.\n");
    }

    // 최대값 찾기
    float max_m=0;
    float max_t=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(max_m<M[i][j])   max_m=M[i][j];
            if(max_t<T[i][j])   max_t=T[i][j];
        }
    }
    // % 변환
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            M[i][j]=M[i][j]/max_m*100;
            T[i][j]=T[i][j]/max_t*100;
        }
    }
    // 각각의 비율이 적용된 배열 W 저장
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            W[i][j]=r1*M[i][j]+r2*T[i][j];

    // 외판원 함수 실행
    travel(n, W, P);

    int A = max-1;
    int path[VSIZE+1];
    int temp = 0;

    // 경로 저장
    path[0]=0;
    path[n]=0;
    for(int i=1; i<n; i++){
        A = A-(1<<temp);
        temp = P[temp][A];
        path[i] = temp;
    }

    // 경로 출력
    printf("Path : [ ");
    for(int i=0; i<n+1; i++)
        printf("v%d ", path[i]+1);
    printf("]\n");

    // 동적할당 해제
    for(int i=0; i<n; i++)
        free(P[i]);
    free(P);

    return 0;
}