试题 D: 最优旅行
本题总分：10 分
【问题描述】
中国的高铁四通八达，乘坐方便，小明经常乘坐高铁在城市间旅游。
现在，小明又有了一个长假，他打算继续乘坐高铁旅游。这次，他打算到
下面的城市旅游。
上海、广州、长沙、西安、杭州、济南、成都、南京、昆明、郑州、天津、
太原、武汉、重庆、南昌、长春、沈阳、贵阳、福州。
小明打算从北京出发，游览以上每个城市正好一次，最终回到北京。在每
个城市（除北京外），小明都至少停留 24 小时。而当小明决定从一个城市去往
另一个城市时，他只会选择有直接高铁连接的城市，不会在中途换乘转车。
在试题目录下有一个文件 trip.txt 保存了小明可以选择的车次，小明不会
选择其他车次。
小明出发的时间是第 1 天的中午 12:00。请问，小明游览完以上城市正好一
次，最终回到北京，最快需要多少分钟（请注意单位为分钟，请注意除北京外
的城市需要至少停留 24 小时，即最少停留 1440 分钟）。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

点击此处下载 trip.txt

这道题，没有很好的思路，因为本人不会算法，还望路过的大佬多多指教。

这题最能想到的就是一个个试，需要很长时间。

代码经过优化后，已经缩短到1分钟左右出结果。

以下是我的结果：

答案：41613

车次    出发地   目的地  发车     到达    乘车时间/分钟 

G8901    北京    天津    22:10    22:45     35
G2609    天津    太原    10:40    14:15    215
G688      太原    郑州    17:38    21:38    240
G2001    郑州    西安     7:52     10:24    152
G2231    西安    重庆    17:6      22:56    350
G8594    重庆    成都     6:50      8:7        77
G2883    成都    昆明     8:51     14:29    338
G1514    昆明    南昌     16:0     22:54    414
G5314    南昌    福州     8:13     11:9      176
G1636    福州    上海    12:26    16:55    269
G7355    上海    杭州    21:30    22:28     58
G7604    杭州    南京    12:9      13:30     81
G579      南京    长沙    9:27      14:10    283
G6117    长沙    广州    17:55     20:39   164
G2960    广州    贵阳     7:27     13:43    376
G1524    贵阳    武汉    14:23    19:33    310
G1274    武汉    沈阳     7:23     19:3      700
G8033    沈阳    长春     6:42      8:40     118
G1242    长春    济南    15:33    22:35    422
G336      济南    北京     7:45      9:33     108

最开始我在网上看到仅有的一个答案40173，由于他的代码没有注释，根本没心情看下去。

测试很多次，各种调整代码，发现我的结果还是41613，后来我发现两个答案只是差了1440，也就是相差了一天的时间数。

或者是我代码多加了一天，或者他代码少加了一天。由于我检查了很多遍代码，看不出我的错误（也可能是当局者迷）。

我决定还是先坚持自己的答案吧（有谁知道正确答案欢迎指正）。

代码思路应该没啥好说的，就是简单的暴力搜索。

需要注意的是：因为暴力搜索时间很长，尽量避免字符串的处理，使用字符串省力气，但是运行时间可能要翻很多很多倍。

因此我将地名转化成对应的序号，将字符串的时间用自定义类加以处理，变为两个int型处理效率肯定要高很多。

我这里使用固定数组来存放火车全部信息

（之前用的List效率很低，因为搜索的过程需要大量的遍历火车全部信息）

代码如下：（代码好像很多的样子，其实可能是我加的注释比代码还多，其实并不长）

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	// 时间类，用于存放和处理时间
	class Time {
		int hour;
		int min;
		public Time(String s) {
			this.hour = Integer.parseInt(s.substring(0, s.indexOf(":")));
			this.min = Integer.parseInt(s.substring(s.indexOf(":") + 1));
		}

		// 转字符串，测试用
		public String toString() {
			return hour + ":" + min;
		}

		// 获取时间差
		public int getMin(Time t) {
			return (hour - t.hour) * 60 + min - t.min;
		}

		// 比较自身是否大于等于传入的时间
		// 先比较时hour，在比较分min
		public boolean isbig(Time t) {
			if (hour > t.hour) {
				return true;
			} else if (hour < t.hour) {
				return false;
			} else {
				if (min >= t.min) {
					return true;
				} else {
					return false;
				}
			}

		}
	}

	// 存放一条火车信息
	class TrainInfor {
		String tn;// 车号
		int start;// 出发地
		int end;// 目的地
		Time starTime;// 出发时间
		Time endTime;// 到达时间
		int min;// 坐火车花费多少分钟

		public TrainInfor(String tn1, int s, int e, String st, String et) {
			this.tn = tn1;
			this.start = s;
			this.end = e;
			this.starTime = new Time(st);
			this.endTime = new Time(et);
			this.min = endTime.getMin(starTime);
		}

		// 转字符
		public String toString() {
			return tn + "\t" + place[start] + "\t" + place[end] + "\t" + starTime.toString() + "\t" + endTime.toString()
					+ "\t" + min;
		}
	}

	// 所有地点
	String[] place = { "北京", "上海", "广州", "长沙", "西安", "杭州", "济南", "成都", "南京", "昆明", "郑州", "天津", "太原", "武汉", "重庆", "南昌",
			"长春", "沈阳", "贵阳", "福州" };
	// 建立访问标记
	boolean[] vis = new boolean[place.length];
	TrainInfor[] ttt = new TrainInfor[132];
	int min = Integer.MAX_VALUE;// 最小值
	boolean once = false;// 是否拿到一次结果;

	public Main() {
		// 读取火车信息存储到list
		try {
			FileReader fr = new FileReader(new File("D:/trip.txt"));
			BufferedReader br = new BufferedReader(fr);
			br.readLine();
			String str;
			int count = 0;
			while ((str = br.readLine()) != null) {
				String[] ss = str.split("\\s+");
				if (ss[0].equals("")) {
					ttt[count] = new TrainInfor(ss[1], getNum(ss[2]), getNum(ss[3]), ss[4], ss[5]);
				} else {
					ttt[count] = new TrainInfor(ss[0], getNum(ss[1]), getNum(ss[2]), ss[3], ss[4]);
				}
				count++;
			}
			br.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
		// 设置时间为12:00开始
		Time t = new Time("12:00");
		// 获取北京直达车票信息
		dfs(0, 0, t);
		System.out.println("最小时间" + min);
	}
    //这个只是最初读入数据的时候，将地名转化成序号用的
	public int getNum(String s) {
		for (int i = 0; i < place.length; i++)
			if (place[i].equals(s))
				return i;
		return 0;
	}

	// 本次刚刚到达的地点 p ， 当前累计旅游的时长 minute分钟 ， 到达时间点t
	public void dfs(int p, int minute, Time t) {
		// 返回北京，但是时长肯定要大于0，minute主要防止最开始时传入0的情况
		if (p == 0 && minute > 0) {
			// 发现更小的值，进行替换
			if (min > minute) {
				min = minute;
				once = true;
				System.out.println("更新了最小值为" + minute);
			}
			return;// 结束
		}
		// 如果这不是北京，最少休息一天
		if (p != 0)
			minute += 1440;
		List<TrainInfor> goodlist = getaimlist(p);//拿到p地点的直达车信息
		for (TrainInfor ti : goodlist) {
			// 如果当前列车到北京，需要先检查一下是不是全部旅游完了，不是的话，不符合条件，跳过
			if (ti.end == 0) {
				vis[0] = true;
				if (!isall()) {
					vis[0] = false;
					continue;
				}
				vis[0] = false;
			}
			// 计算时间
			int time = minute;
            //注意：当前的time是已经休息过一天，开始等火车
			// 当前列车发车时间点比之前下车时间点晚，说明今天就能坐车
			if (ti.starTime.isbig(t)) {
				// 加上等待火车时间，和坐火车时间
				time += (ti.starTime.getMin(t) + ti.min);
			} else {
				// 否则等明天坐上车
				// 这里ti.starTime.getMin(t)得到的是个负值+一天的时间，会得到等待火车的时间
				time += (ti.starTime.getMin(t) + 1440 + ti.min);
			}
			// once是否已经求出一个最小值
			// 小小的剪枝，如果还没到北京，所用时间已经比当前最小值多，就没必要往下进行了。
			if (once)
				if (time > min)
					continue;
			// 访问
			vis[ti.end] = true;
			// 传入，到达的地点，总时间，到达时间点
			dfs(ti.end, time, ti.endTime);
			vis[ti.end] = false;
		}
	}

	// 当前所有地点是不是全部访问完毕。
	public boolean isall() {
		for (boolean isno : vis)
			if (!isno)
				return false;
		return true;
	}

	// 获取p当地直达的火车信息
	public List<TrainInfor> getaimlist(int p) {
		// 创建个表准备存放
		List<TrainInfor> fulist = new ArrayList<TrainInfor>();
		// 遍历信息
		for (int i = 0; i < 132; i++) {
			// 只要出发地为p，目的地未访问过的，都加入列表
			if (ttt[i].start == p && !vis[ttt[i].end]) {
				fulist.add(ttt[i]);
			}
		}
		return fulist;
	}

	public static void main(String[] args) {
		new Main();

	}
}

完毕