import ;
public class huisu {
public static int cityNum; // 城市总数
public static int disNum; // 路径总数
public static int[][] disArray; // 存储城市间距离
public static int shortDis = Integer.MAX_VALUE; // 记录最短路径长度
public static int nowDis = 0; // 记录这次遍历过程中的路径长度
public static int[] shortDisArray; // 最短路径经过的城市顺序
public static int[] nowDisArray; // 记录这次遍历过程中的经过的城市顺序
public static int cout = 0; // 计数器，表示现在走了几个城市
public static boolean[] isPass; // 表示是否遍历过
public static void huisu(int now) {
// 如果全部城市走完
if (cout == cityNum) {
int start = nowDisArray[0]; // 找出初始城镇
// 如果最后一个城镇能否回到初始城镇
if (disArray[now][start] != -1) {
nowDis+= disArray[now][start]; // 添加最后城镇回初始城镇的路程
// 如果比记录的最短路径短
if (nowDis <= shortDis) {
shortDis = nowDis;
System.arraycopy(nowDisArray, 0, shortDisArray, 0, nowDisArray.length);
}
}
}
// 如果还没走完路径已经比记录的最短路径长了，那就没必要继续走了
if (nowDis > shortDis) return;
// 没有走完就从现在的城市开始遍历
for (int j = 0;j < cityNum;j++) {
// 下一个打算走的城市为-1，不可达，不选这个
if (disArray[now][j] == -1) continue;
// 如果城市已经走过了，不选这个
if (isPass[j]) continue;
// 满足条件，可以选择走
isPass[j] = true; // 将这个暂时设定为走过
nowDis+= disArray[now][j]; // 添加距离到总路径长度
nowDisArray[cout++] = j; // 将经过城市记录到顺序中
huisu(j); // 进入下一个选择
isPass[j] = false; // 回溯，改回未走过
nowDis-= disArray[now][j]; // 回溯，减掉这段路径
cout--; // 回溯，减掉这段路径
}
}
public static void main(String[] args) {
// 初始化参数
Scanner scan = new Scanner(System.in);
System.out.println("请输入城市总数：");
cityNum = scan.nextInt(); // 城市总数
System.out.println("请输入路径总数：");
disNum = scan.nextInt(); // 路径总数
int nowDisNum = 0; // 现在已经输入的路径数
int a = -1; // 第一个城市的编号
int b = -1; // 第二个城市的编号
int d = -1; // 两城市间距离
disArray = new int[cityNum][cityNum]; // 存储城市间距离
shortDisArray = new int[cityNum]; //
nowDisArray = new int[cityNum];
isPass = new boolean[cityNum];
// 城市间距离初始化为 -1，表示不可达
for (int i = 0;i < cityNum;i++) {
for (int j = 0;j < cityNum;j++) {
disArray[i][j] = -1;
}
}
for (int i = 0;i < cityNum;i++) {
shortDisArray[i] = -1;
nowDisArray[i] = -1;
}
// 循环录入城市间距离
while (nowDisNum < disNum) {
// 输入第一个城市时只要判断编号是否正常就行
System.out.println("请输入第一个城市的编号（0 - " + (cityNum-1) + ")");
a = scan.nextInt();
if (a < 0 || a >= cityNum) {
System.out.println("输入参数有误，请重新输入");
continue;
}
// 第二个城市需要判断编号是否正常，是否是不同城市，是否已经录入过
System.out.println("请输入第二个城市的编号（0 - " + (cityNum-1) + ")");
b = scan.nextInt();
if (b < 0 || b >= cityNum) {
System.out.println("输入参数有误，请重新输入");
continue;
}else if (a == b) {
System.out.println("不能输入同个城市，请重新输入");
continue;
}else if (disArray[a][b] != -1) {
System.out.println("这两个城市间的距离已存在，请重新输入");
continue;
}
// 录入距离时判断距离是否为正整数
System.out.println("请输入这两个城市间的距离：");
d = scan.nextInt();
if (d < 0) {
System.out.println("输入参数有误，请重新输入");
continue;
}
// 录入数据到二维数组中
disArray[a][b] = disArray[b][a] = d;
System.out.println("输入成功");
nowDisNum++;
}
// 开始求解，假设每个城市作为起点
for (int i = 0;i < cityNum;i++) {
isPass[i] = true;
nowDisArray[cout++] = i;
huisu(i);
isPass[i] = false;
nowDisArray[--cout] = -1;
}
// 返回结果
if (shortDisArray[0] == -1) {
System.out.println("无法找到经过所有城市一次的最短路径");
}else {
System.out.println("最短路径长度：" + shortDis);
System.out.print("经过的城市编号为：");
for (int i = 0;i < cityNum;i++) {
System.out.print(shortDisArray[i] + " ");
}
System.out.print(shortDisArray[0]);
}
}
}