回溯法求旅行售货员问题

#include<iostream>
using namespace std;
const int INF = 10000000;
int n, cc = 0, bestc = INF;//n表示几个点，cc表示当前的距离bestc表示最优的距离，bests
//开始时赋值最大值
int **g;//二维数组g中存储各点间距离
int *x, *bestx;//x数组中存储点的信息
void travel(int t){
 if(t == n){
  if (g[x[t - 1]][x[t]] != INF && g[x[t]][1] != INF &&
   (cc + g[x[t - 1]][x[t]] + g[x[t]][1] < bestc || bestc == INF)) {
    bestc=cc + g[x[t - 1]][x[t]] + g[x[t]][1];
    for(int i = 0; i < n+1; i++){
     bestx[i] = x[i];
    }
 }
 return ;
}
else{
 for(int i = t; i < n; i++){
  if(g[x[t-1]][x[i]] != INF && g[x[t-1]][x[i]]+cc < bestc || bestc == INF){
   swap(x[i],x[t]);
   cc += g[x[t-1]][x[t]];
   travel(t+1);
   cc -= g[x[t-1]][x[t]];
   swap(x[i],x[t]);
  }
 }
}
}
void output(){
 cout << bestc << endl;
 cout <<bestx[1] <<" ";
 for(int i=2; i < n+1; i++){
  cout << bestx[i] << " ";
 }
 cout << bestx[1] << endl;
}
int main() {
 n = 4;
 g = new int*[n + 1];
 x = new int[n + 1];
 bestx = new int[n + 1];
 for (int i = 0; i < n + 1; i++) {
  g[i] = new int[n + 1];
  x[i] = i;
  for (int j = 0; j < n + 1; j++)
   g[i][j] = INF;
 }
 g[1][2] = g[2][1] = 30;
 g[1][3] = g[3][1] = 6;
 g[1][4] = g[4][1] = 4;
 g[2][3] = g[3][2] = 5;
 g[2][4] = g[4][2] = 10;
 g[3][4] = g[4][3] = 20;
 travel(2);//从第二层开始判断
 output();
 return 0;
}