旅行售货员问题

template <class Type>
class Traveling {
    friend Type TSP(int**, int[], int, Type);
private:
    void Backtrack(int i);
    int n, *x, *bestx;
    Type **a, cc, bestc, NoEdge;
};

template <class Type>
void Traveling<Type>::Backtrack(int i) {
    if (i == n) {
        if (a[x[n - 1]][x[n]] != NoEdge && a[x[n]][1] != NoEdge && (cc + a[x[n - 1]][x[n]] + a[x[n]][1] < bestc || bestc == NoEdge)) {
            for (int j = 1; j <= n; j++) {
                bestx[j] = x[j];
            }
            bestc = cc + a[x[n - 1]][x[n]] + a[x[n]][1];
        }
    } else {
        for (int j = i; j <= n; j++) {
            if (a[x[i - 1]][x[j]] != NoEdge && (cc + a[x[i - 1]][x[j]] < bestc || bestc == NoEdge)) {
                Swap(x[i], x[j]);
                cc += a[x[i - 1]][x[i]];
                Backtrack(i + 1);
                cc -= a[x[i - 1]][x[i]];
                Swap(x[i], x[j]);
            }
        }
    }
}

template <class Type>
Type TSP(int **a, int v[], int n, Type noEdge) {
    Traveling<Type> Y;
    Y.x = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        Y.x[i] = i;
    }
    Y.a = a;
    Y.n = n;
    Y.bestc = noEdge;
    Y.bestx = v;
    Y.cc = 0;
    Y.NoEdge = noEdge;
    Y.Backtrack(2);
    delete [] Y.x;
    return Y.bestc;
}