TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3100
  • 题目
  • P3100树的最长链
    限制 : 时间限制 : 10000 MS   空间限制 : 165536 KB
    问题描述

    乌托邦有n个城市,某些城市之间有公路连接。任意两个城市都可以通过公路直接或者间接到达,并且任意两个城市之间有且仅有一条路径。每条公路都有自己的长度,这些长度都是已经测量好的。
    小修想从一个城市出发开车自驾游到另一个城市,并且她希望经过的公路总长度最长。请问她应该选择哪两个城市?这个最长的长度是多少?(路上不能重复经过某个城市)

    输入格式

    第一行n(n <= 1000)。
    以下n-1行每行三个整数a, b, c。表示城市a和城市b之间有公路直接连接,并且公路的长度是c(c <= 10000)。

    输出格式

    仅一个数,即最长长度。

    样例输入

    5
    1 2 2
    2 3 1
    2 4 3
    1 5 4

    样例输出

    9

    提示

    说明:从城市4到城市5,经过的路径是4-2-1-5,总长度是9。