#include<bits/stdc++.h> // 包含標準庫的頭文件using namespace std; // 使用標準命名空間template <class Type> // 模板聲明，Type為類型參數
class Traveling{ // 定義Traveling類friend Type Tsp(int **, int[],int, Type); // 聲明友元函數Tsp
public:int predict(int j);void Backtrack(int i); // 聲明Backtrack函數int n, *x, *bestx; // 聲明成員變量n頂點數目, x存放當前解的結點編號, bestx存放最優解的結點編號Type **a, cc, bestc; // 聲明成員變量a鄰接矩陣, cc當前已經求得的費用, bestc最佳費用
};template <class Type> // 模板聲明，Type為類型參數
Type Tsp(Type **a, int v[], int n); // 聲明Tsp函數int min_edge = INT_MAX;int main() // 主函數入口
{clock_t start = clock();int **a,*v, n,bestc; // 聲明指針變量和整型變量cin>>n; // 輸入n的值v= new int[n+1]; // 動態分配數組v的內存空間a=new int* [n+1]; // 動態分配數組a的內存空間for(int i=0;i<=n;i++) // 循環，初始化數組a的每一行a[i]=new int [n+1]; // 動態分配數組a的每一行的內存空間for(int i=1;i<=n;i++) // 循環，輸入每一行的數據for(int j=i+1;j<=n;j++){ // 循環，輸入每一行的數據cin>>a[i][j]; // 輸入數據到數組aa[j][i]=a[i][j]; // 將對稱位置的數據設為相同的值if(i == 1 && a[i][j] < min_edge) min_edge = a[i][j]; }bestc=Tsp(a,v,n); // 調用Tsp函數計算最短路徑長度cout << bestc << endl; // 輸出最短路徑長度clock_t end = clock();float duration = (float)(end - start) / CLOCKS_PER_SEC;cout << duration;return 0; // 返回0，表示程序正常結束
}template <class Type>
int Traveling <Type>::predict(int j)
{int sum = 0;int *sign = new int[n+1];memset(sign, 0, sizeof(sign));for(int i = 1; i <= j; i++) sign[x[i]] = 1;for(int i = j; i <= n; i++){int smallest = INT_MAX, small = INT_MAX;int vertex = x[i];for(int to = 1; to <= n; to++){if(sign[to] || to == vertex) continue;if(a[vertex][to] < smallest) {small = smallest; // 將原來的最小值賦給次小值smallest = a[vertex][to]; // 更新最小值}else if(a[vertex][to] < small) {small = a[vertex][to]; // 更新次小值}}if(small != INT_MAX) sum += small, sum += smallest;else if(smallest != INT_MAX) sum += smallest*2;}return sum/2 + min_edge;
}template <class Type> // 模板聲明，Type為類型參數
void Traveling <Type>::Backtrack(int i) // 類Traveling成員函數Backtrack的實現
{cout << bestc;puts("");int temp; // 聲明臨時變量tempif(i==n){ // 如果i等于nif(a[x[n-1]][x[n]]!=0 && a[x[n]][x[1]]!=0 && // 如果路徑形成一個環(cc+a[x[n-1]][x[n]]+a[x[n]][x[1]]<bestc || bestc ==0)){ // 并且路徑長度小于最優長度或者最優長度為0for(int j=1;j<=n;j++) // 循環，復制當前路徑到最優路徑bestx[j]=x[j]; // 復制當前路徑到最優路徑bestc=cc+a[x[n-1]][x[n]]+a[x[n]][x[1]]; // 更新最優路徑長度}}else{ // 否則for(int j=i;j<=n;j++) // 循環，嘗試不同的下一個城市if(a[x[i-1]][x[j]]!=0 && // 如果下一個城市可達(cc+a[x[i-1]][x[j]]+predict(j)<bestc || bestc==0)){ // 并且路徑長度小于最優長度或者最優長度為0temp=x[i]; // 交換城市順序x[i]=x[j]; // 交換城市順序x[j]=temp; // 交換城市順序cc+=a[x[i-1]][x[i]]; // 更新路徑長度Backtrack(i+1); // 遞歸調用Backtrack函數cc-=a[x[i-1]][x[i]]; // 恢復路徑長度temp=x[i]; // 交換城市順序x[i]=x[j]; // 交換城市順序x[j]=temp; // 交換城市順序}}
}template <class Type> // 模板聲明，Type為類型參數
Type Tsp(Type **a, int v[], int n) // 函數Tsp的實現
{Traveling <Type> Y; // 聲明Traveling類的實例YY.x=new int[n+1]; // 動態分配數組Y.x的內存空間for(int i=1;i<=n;i++) // 循環，初始化Y.x數組Y.x[i]=i; // 初始化Y.x數組Y.a=a; // 將參數a賦值給Y.aY.n=n; // 將參數n賦值給Y.nY.bestc=0; // 將Y.bestc初始化為0Y.bestx=v; // 將參數v賦值給Y.bestxY.cc=0; // 將Y.cc初始化為0Y.Backtrack(2); // 調用Backtrack函數計算最短路徑delete [] Y.x; // 釋放Y.x的內存空間return Y.bestc; // 返回最短路徑長度
}

predict函數采用貪心策略，搜索剩余結點之間（可從x[j]開始，但不到x[j]，因為判斷中已經把x[i-1]到x[j]的長度考慮了，不屬于未知部分，所以這是約束不是預測）的最短和次短鄰接邊，然后取平均再分別求和，作為對到剩余結點的預測。也就是說原本的代碼不存在限界函數，只有約束函數，我們加入了限界函數，進一步完成了剪枝。(注意加上返回1的最短邊)