package lvxingshang;
import java.util.Scanner;
public class Bttsp {
static int n; //图G的顶点数
static int[]x; //当前解
static int[]bestx; //当前最优解
static float bestc; //当前最优值
static float cc; //当前费用
static float[][]a; //图G的邻接矩阵
public static float tsp(int[]v)
{
//置x为单位矩阵
x=new int[n+1];
for(int i=1;i<=n;i++)
{x[i]=i;}
bestc=Float.MAX_VALUE;
bestx=v;
cc=0;
System.out.println("最低路费为：");
backtrack(2);
for(int i=1;i<=n+1;i++)
{
int j = 0;
j = i;
if(i==5)
{
j=1;
}
System.out.print(bestx[j]);
}
return bestc;
}
private static void backtrack(int i)
{
if(i==n)
{
if(a[x[n-1]][x[n]]<Float.MAX_VALUE&&a[x[n]][1]<Float.MAX_VALUE&&(bestc==Float.MAX_VALUE||cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc))
{
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++)
//是否可以进入x【j】子树？
if(a[x[i-1]][x[j]]<Float.MAX_VALUE&&(bestc==Float.MAX_VALUE||cc+a[x[i-1]][x[j]]<bestc))
{
//搜索子树
MyMath.swap(x,i,j);
cc+=a[x[i-1]][x[j]];
backtrack(i+1);
cc-=a[x[i-1]][x[j]];
MyMath.swap(x,i,j);
}
}
}
public static class MyMath{
public static void swap(int[] x, int i, int j) {
int temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
public static void main(String[] args){
Scanner s=new Scanner(System.in);
System.out.println("请输入售货员要去的城市个数：");
String line=s.nextLine();//读入n
n=Integer.parseInt(line);
a=new float[n+1][n+1];
int []vv=new int[n+1];
System.out.println("请输入来往各个城市之间的花费：若城市个数为2，则输入：0 * \n"+
" * 0");
for(int i=0;i<n;i++){
line=s.nextLine();
String []sArray=line.split(" ");
for(int j=0;j<sArray.length;j++){
a[i+1][j+1]=Integer.parseInt(sArray[j]);
}
}
System.out.println(tsp(vv));
}
}