TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3497
  • 题目
  • P3497火车铁路
    限制 : 时间限制 : 10000 MS   空间限制 : 165536 KB
    问题描述

    某个国家的铁路网是由若干段铁路段构成的,每段铁路段连接两个不同的城市,且长度是已知的,任意两个城市之间有且仅有一条由铁路段连接起来的路径。
    最近铁道部决定将所有的老火车头都换成国外进口的新火车头,由于新火车头速度很快,任意两趟列车都不可以经过相同的城市,以免发生相撞事故,铁道部需要编制新的列车行驶路线,每一条路线由二个(包括二个)以上的城市构成,且相邻两个城市间有铁路段直接相连,这些铁路段的长度总和即为该路线的长度。每一个城市都必须出现在某一条线路上,任意两条路线不能有相同的城市。写一个程序求出最佳的路线编排,使得全部路线的总长度最大。

    输入格式

    第一行包含一个整数N,表示城市总数,所有城市被依次编号为1 到N。
    接下来的N-1 行包含每一段铁路的描述,每一行包含三个用空格隔开的整数A,B 和C,表示城市A与B 之间有一段铁路,其长度为C,其中1≤C≤1,000,000。
    注意对所有的测试数据,问题总有解。

    输出格式

    一行包含一个整数,表示要求的最大的路线总长度。

    样例输入


    样例输出

    样例输入1 
    9
    1 2 1
    2 4 2
    3 4 1
    4 5 5
    6 5 1
    5 7 2
    7 8 1
    8 9 2

    样例输入2
    11
    9 10 10
    1 11 8
    5 6 2
    1 7 8
    6 1 7
    7 8 3
    1 2 9
    10 11 7
    3 4 4
    2 3 10

    提示

    样例输出1
    11

    样例输出2
    53

    【样例1 解释】
    共3 条铁路,分别是:
    1——2
    3——4——5——6
    7——8——9
    【数据范围】
    对于30%的数据1 ≤ N ≤ 100
    对于100%的数据1 ≤ N ≤ 2000 ,1 ≤ D ≤1000000