旅行售货员（回溯法）

标题：	旅行售货员
时 限：	1000 ms
内存限制：	10000 K
总时限：	3000 ms
描述：	某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（ 或旅费）最小。各个城市之间可能是有向连通的、无向连通的、以及存在某个城市不连通的情况，你的程序应该能够处理所有可能的情况。如下图表示各个城市间无向连通。
输入：
输出：
输入样例：	4 -1 -1 -1 2 2 -1 -1 -1 1 3 -1 -1 -1 -1 1 -1
输出样例：	8
提示：

import java.util.Scanner;

public class Main {
    static int n = 0; // 图的顶点数
    static int[] x = null; // 当前解
    static int[] bestx = null; // 当前最优解
    static float bestc = 0; // 当前最优值
    static float cc = 0; // 当前费用
    static float[][] a = null; // 领接矩阵
    
    public static void backtrack(int i){
        if(i==(n-1)){
            if(a[x[i-1]][x[i]]!=-1&&
                 a[x[i]][x[0]]!=-1&&
                 (bestc==-1||cc+a[x[i-1]][x[i]]+a[x[i]][0]<bestc))
            {
                for(int j=0;j<n;j++)
                    bestx[j]=x[j];
                bestc=cc+a[x[i-1]][x[i]]+a[x[i]][0];
            }
        }    else{
            for(int j=i;j<n;j++){
                if(a[x[i-1]][x[j]]!=-1&&
                        (bestc==-1||cc+a[x[i-1]][x[j]]<bestc)){
                    Swap(x,i,j);
                    cc+=a[x[i-1]][x[i]];
                    backtrack(i+1);
                    cc-=a[x[i-1]][x[i]];
                    Swap(x,i,j);
                }
            }
        }
    }
    
    public static void Swap(int[] x, int i, int j) {
        int temp;
        temp = x[i];
        x[i] = x[j];
        x[j] = temp;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method
        Scanner myscanner = new Scanner(System.in);
        n = myscanner.nextInt();

        a = new float[n][n ];
        bestx = new int[n ];
        x = new int[n];
        bestc = -1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = myscanner.nextFloat();
            }
        }
        for (int i = 0; i < n; i++) {
            x[i] = i;
        }

        Main.backtrack(1);

        System.out.println((int) bestc);

        /*
         * for (int j = 1; j <= n; j++) { System.out.println(bestx[j]); }
         */
    }
}