/Educational Backtracking: Đi dạo

              #include <algorithm>
        #include <iterator>
        #include <iostream>
        
        using namespace std;
        
        int arr[100][100];
        int trace[100] = { 0 };
        int result[100];
        bool check[100];
        
        long long sum = 0;
        long long best = 1e9 + 7;
        int best1 = 0;
        int n, k;
        
        void update(long long& sum, int* trace) {
          //	for (int i = 0; i < k; i++) {
          //		cout << *(trace + i) + 1 << " ";
          //	}
          //	cout << endl;
          if (best > sum + arr[trace[k - 1]][0]) {
            best = sum + arr[trace[k - 1]][0];
            for (int i = 0; i < k; i++) {
              result[i] = trace[i];
            }
          }
          if (best1 > best) best1 = best;
        }
        
        void action(int bound) {
          //if (sum >= best) return;
          if (best / (k + 1) == 1) return;
          for (int i = 1; i < n; i++) {
            if (check[i] == false && bound < k) {
              trace[bound] = i;
              sum = sum + arr[trace[bound - 1]][i];
              check[i] = true;
              if (bound == k - 1) {
                update(sum, trace);
              }
              else if (sum < best1) {
                action(bound + 1);
              }
              check[i] = false;
              trace[bound] = 0;
              sum = sum - arr[trace[bound - 1]][i];
            }
          }
        }
        
        int main() {
        
          cin >> n >> k;
        
          for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
              cin >> arr[i][j];
            }
          }
        
          int c[100];
          c[0] = 0;
          bool d[100] = {false};
          d[0] = true;
        
          for (int i = 1; i < k; i++) {
            int select = 1e9 + 7;
            for (int j = 1; j < n; j++) {
              if (d[j] == false && arr[c[i - 1]][j] < select) {
                select = arr[c[i - 1]][j];
                c[i] = j;
              }
            }
            d[c[i]] = true;
            best1 = best1 + arr[c[i - 1]][c[i]];
          }
          best1 = best1 + arr[c[k - 1]][0];
          //cout << best1 << endl;
          trace[0] = 0;
          check[0] = true;
          //cout << "E" << endl;
          action(1);
        
        
          cout << best << endl;
        
          for (int i = 0; i < k; i++) {
            cout << *(result + i) + 1 << " ";
          }
        
          return 0;
        }