问题2141--旅行商变形2（HDU3001）

2141: 旅行商变形2（HDU3001）

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交] [状态] [讨论版] [命题人:]

题目描述

阿克默决定参观n 个城市，他要参观所有城市，不介意哪座城市是他的起点。有m 条道路照常收费，但他不想去一座城市超过两次，想把总费用降到最低。

输入

输入包含几个测试用例，每个测试用例的第1行都包含两个整数n （1≤n ≤10）和m ，表示n 个城市、m 条道路。接下来的m行，每行都包含三个整数a 、b 和c （1≤a ，b ≤n ），表示在a 和b 之间有一条道路，费用是c 。

输出

对每个测试用例，都单行输出应支付的最低费用，若找不到这样的路线，则输出-1。

样例输入 Copy 

2 1
1 2 100
3 2
1 2 40
2 3 50
3 3
1 2 3
1 3 4
2 3 10

样例输出 Copy 

100
90
7

来源/分类

动态规划算法 状压DP 
[提交] [状态]