TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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