TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1905
  • 题目
  • P1905【S2状态压缩】慢跑小路
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    Gord准备参加马拉松赛跑,他在家的后面的一个公园进行练习。公园里面有很多设置有座椅和饮用水的休息点,庞大的慢跑小路构成的道路网将这些休息点连接了起来。Gord想要找出最短的一条慢跑小路路径,要求这条路径将每条小路都至少经过了一次。

    输入格式

    输入有多组数据,对于每组数据:
    第一行,两个整数n和m,分别表示休息点的数量和小路的数量。
    接下来m行,每行包含三个整数x,y,z,代表一条小路的信息,在休息点x和休息点y之间有条长度为z的慢跑小路。
    注意:两个休息点之间有可能有多条慢跑小路直接相连。Gord可以选择任意休息点作为起点,但是路径的终点和起点必须相同。
    单独的一行一个数字0表示输入结束。

    输出格式

    对于每组测试数据,输出一行,每行一个整数,表示最短路径的长度。

    样例输入

    4 5
    1 2 3
    2 3 4
    3 4 5
    1 4 10
    1 3 12
    0

    样例输出

    41

    提示

    n <= 15
    m < 1000
    z<=10000


    来源  Waterloo local 2002