题目 1945:
蓝桥杯算法提高VIP-Subway Timing
时间限制: 2s
内存限制: 192MB 提交: 4 解决: 0
题目描述
和很多现代化的城市一样，斯德哥尔摩有一个发达的公共交通系统。而斯德哥尔摩公共交通的核心就是地铁。一份地铁的拓扑地图里有不同的地铁线路，以及他们之间的连接方式，如下图。在这个问题中，你可以假定地铁的地图一定是树形的，尽管斯德哥尔摩的地铁实际上并非确实如此，例如图中蓝色和绿色的线路形成了一个环。
地铁的拓扑图并不关心地铁系统的几何性质，比如说不同地铁站之间的距离（以及相应的旅行时间）。虽然斯德哥尔摩的大部分学生都知道，“Tekniska Hogskolan” (皇家理工学院) 和 “Universitetet” (斯德哥尔摩大学)相隔是非常远的，但是如上这幅图中却没有体现出来。
为了丰富这张地图，你要写一个程序，计算出任意相邻地铁站之间所需的旅行时间。幸运的是，那些旅行时间是已知的，所以不需要你亲自去测量。但问题是，实际测量出来的时间是以秒为单位，而画在地图上的时间却是以分钟为单位，而且必须是整数，所以需要你给出一个时间的估计。
一种自然的估计时间的方法可能是简单地将所有的旅行时间转往离其最近的整数取整。但是这有可能导致巨大的累计误差。在斯德哥尔摩的地图上，这种估计方法会导致在某两个地铁站之间的旅行时间的估计与实际时间出现一个将近15分钟的偏差。为了避免这个，你的程序需要选择一些相邻地铁站之间的旅行时间向上取整，其余的向下取整，从而使得点对之间最大的累计误差最小。
地铁的拓扑图并不关心地铁系统的几何性质，比如说不同地铁站之间的距离（以及相应的旅行时间）。虽然斯德哥尔摩的大部分学生都知道，“Tekniska Hogskolan” (皇家理工学院) 和 “Universitetet” (斯德哥尔摩大学)相隔是非常远的，但是如上这幅图中却没有体现出来。
为了丰富这张地图，你要写一个程序，计算出任意相邻地铁站之间所需的旅行时间。幸运的是，那些旅行时间是已知的，所以不需要你亲自去测量。但问题是，实际测量出来的时间是以秒为单位，而画在地图上的时间却是以分钟为单位，而且必须是整数，所以需要你给出一个时间的估计。
一种自然的估计时间的方法可能是简单地将所有的旅行时间转往离其最近的整数取整。但是这有可能导致巨大的累计误差。在斯德哥尔摩的地图上，这种估计方法会导致在某两个地铁站之间的旅行时间的估计与实际时间出现一个将近15分钟的偏差。为了避免这个，你的程序需要选择一些相邻地铁站之间的旅行时间向上取整，其余的向下取整，从而使得点对之间最大的累计误差最小。
输入格式
输入包含多组数据。每组数据最开始是一个整数N(1≤N≤100)，为地铁站的个数。这N个地铁站用正整数1到N标记。接下来N-1行包含了三个整数a,b,t(1≤a,b≤n,1≤t≤300)，表示地铁站a和站b是相邻的，而且在它们之间旅行的时间花费是t秒。为了简化问题，忽略地铁在地铁站停留的时间。
输入以EOF结束。
输入以EOF结束。
输出格式
对于每组数据，输出数据组号（从1开始标号），然后输出对相邻地铁站之间的旅行时间进行舍入之后，两两地铁站之间旅行时间误差的最大值所能取到的最小值。具体参照样例所给定的格式。
样例输入
2 1 2 110 4 1 2 40 2 3 40 3 4 40 4 1 2 90 1 3 90 1 4 90
样例输出
Case 1: 10 Case 2: 40 Case 3: 60