首页 > 其他 > 详细

COJ 0288 路径(2015升级版)

时间:2015-08-03 20:40:31      阅读:167      评论:0      收藏:0      [点我收藏+]

路径(2015升级版)
难度级别:D; 运行时间限制:1000ms; 运行空间限制:262144KB; 代码长度限制:2000000B
试题描述
WZJ在生日当天决定在他的领地举行一场马拉松比赛,他的领地有N座城市,是通过道路相连组成了一个N-1条边的无向无环图。每条边由ai连到bi,距离为ci。WZJ决定选取两个城市分别为起点和终点,举行比赛。比赛时按这两个城市间的最短距离进行比赛。WZJ想选出一条尽量长的路径,但由于资金限制,路径长最多不能超过k。你能帮帮他吗?
输入
第一行为两个正整数N,k,表示N个城市,最长距离为K。
接下来N-1行为ai,bi,ci,表示有一条边从ai到bi,距离为ci。
输出
输出路径在小于k的情况下的最长长度。
输入示例
5 7
1 2 3
1 3 4
4 5 7
4 2 2
输出示例
7
其他说明
1<=N<=50000 
1<=ai,bi<=N
1<=ci<=k<=10^9
起点为2,终点为3.
放心,不是O(nlog^2n)是过不了的!

COJ 0288 路径(2015升级版)

原文:http://www.cnblogs.com/chxer/p/4700244.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!