TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1905
  • Problem
  • P1905【S2状态压缩】慢跑小路
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

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

    Input Format

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

    Output Format

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

    Sample Input

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

    Sample Output

    41

    Hint

    n <= 15
    m < 1000
    z<=10000


    Source  Waterloo local 2002