tsp16

#include <climits>

bool check_bit(unsigned int bit, int pos) {
    return bit & (1 << pos);
}

unsigned int assign_bit_with_0(unsigned int bit, int pos) {
    return bit & ~(1 << pos);
}

string arr_number_to_string(int arr[], int size) {
    string result;
    for (int i = 0; i < size; ++i) {
        if (arr[i] >= 0 && arr[i] <= 25) {
            result += 'A' + arr[i];
        } else {
            result += '?';
        }
        if (i < size - 1) {
            result += ' ';
        }
    }
    return result;
}

string Traveling(int G[20][20], int n, char character_type) {
    // cout<<n;
    // cout<<character_type;
    int start_vertex = character_type - 'A';
    int max_states = 1 << n;
    int **dp = new int *[max_states];
    int **path = new int *[max_states];
    for (int i = 0; i < max_states; ++i) {
        dp[i] = new int[n];
        path[i] = new int[n];
        for (int j = 0; j < n; ++j) {
            dp[i][j] = INT_MAX;
            path[i][j] = -1;
        }
    }
    dp[1 << start_vertex][start_vertex] = 0;

    for (int mask = 1; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if (!check_bit(mask, i)) continue;
            for (int j = 0; j < n; j++) {
                if (check_bit(mask, j) && i != j && G[j][i] != 0 && dp[assign_bit_with_0(mask, i)][j] != INT_MAX) {
                    int tempCost = dp[assign_bit_with_0(mask, i)][j] + G[j][i];
                    if (tempCost < dp[mask][i]) {
                        dp[mask][i] = tempCost;
                        path[mask][i] = j;
                    }
                }
            }
        }
    }
    int final_mask = (1 << n) - 1;
    int result = INT_MAX;
    int last_city = -1;
    for (int i = 0; i < n; i++) {
        if (i != start_vertex && dp[final_mask][i] < INT_MAX && G[i][start_vertex] != 0) {
            int tempCost = dp[final_mask][i] + G[i][start_vertex];
            if (tempCost < result) {
                result = tempCost;
                last_city = i;
            }
        }
    }

    if (result == INT_MAX) {
        cout << "Không có hành trình nào thỏa mãn." << endl;
        for (int i = 0; i < max_states; ++i) {
            delete[] dp[i];
            delete[] path[i];
        }
        delete[] dp;
        delete[] path;
        return "";
    } else {
        int backtrack_path[n + 1];
        int mask = final_mask;
        int city = last_city;
        int index = n;

        while (city != -1) {
            backtrack_path[index--] = city;
            int temp = mask;
            mask = assign_bit_with_0(mask, city);
            city = path[temp][city];
        }
        backtrack_path[0] = start_vertex;
        int repair_backtrack[n];
        for (int i = 0; i < n; i++) {
            repair_backtrack[i] = backtrack_path[i + 1];
        }
        for (int i = 0; i < max_states; ++i) {
            delete[] dp[i];
            delete[] path[i];
        }
        delete[] dp;
        delete[] path;
        return arr_number_to_string(repair_backtrack, n) + " " + character_type;
    }
}