1927_算法设计例题：旅行售货员问题（回溯、分枝限界）

旅行售货员问题又称TSP问题，问题如下：某售货员要到若干个城市推销商品，已知各城市之间的路程（或旅费），他要选定一条从驻地出发，经过每个城市一遍最后回到驻地的路线，使总的路线（或总的旅费）最小。数学模型为给定一个无向图，求遍历每一个顶点一次且仅一次的一条回路，最后回到起点的最小花费。

输入的第一行为测试样例的个数T，接下来有T个测试样例。

每个测试样例的第一行是无向图的顶点数n、边数m（ 1 < n ≤ 18，m < n×n ），接下来m行，每行三个整数u、v和w，表示顶点u和v之间有一条权值为w的边相连。（ 1 ≤ u < v ≤ n，w ≤ 1000 ）。假设起点（驻地）为1号顶点。

对应每个测试样例输出一行，格式为"Case #: W"，其中'#'表示第几个测试样例（从1开始计），W为TSP问题的最优解，如果找不到可行方案则输出-1。

2
5 8
1 2 5
1 4 7
1 5 9
2 3 10
2 4 3
2 5 6
3 4 8
4 5 4
3 1
1 2 10

Case 1: 36
Case 2: -1