问题1420--Travelling

1420: Travelling

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

题目描述

Acmer先生决定访问n座城市。他可以空降到任意城市，然后开始访问，要求访问到所有城市，任何一个城市访问的次数不少于1次，不多于2次。n座城市间有m条道路，每条道路都有路费。求Acmer先生完成旅行需要花费的最小费用。

输入

第1行是n和m，1≤n≤10；后面有m行，有3个整数a、b、c，表示城市a和b之间的路费是c。

输出

最少花费，如果不能完成旅行，则输出-1。

样例输入 Copy 

2 1
1 2 100

样例输出 Copy 

100

来源/分类

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