3067. Fast & Furious 7

单点时限: 2.0 sec

内存限制: 256 MB

唐门兄弟和肖打赌:

肖:我们玩躲猫猫,保证你 5 小时内找不到我!

唐:在飞车上没人比得过我!

好戏上演,唐门兄弟再次表演空降,假设飞机可以一开始把他们送到任何一个城市(送到城市后,将开始赛车的追逐),这时比赛开始,在鹰眼的帮助下可以迅速知道肖所在的城市(但是在部署人员的时候并不知道),我们必须保证能够在最短时间内到达肖所在的城市,将其抓住。

输入格式

第一行为测试数据组数

对每一组数据,输入三个整数 (), (), () 分别表示 座城市, 条路, 个人来追踪肖。

接下去 行,每一行三个整数 (), 分别表示城市编号, 表示从城市 需要 小时的路程。

输出格式

对于每组数据,先输出 Case #X:,其中 X 表示第几组数据,再输出抓住肖的最短时间,假如无法抓住肖,输出

样例

Input
3
5 4 2
1 2 1
1 3 2
1 4 3
1 5 4
5 4 3
1 2 1
1 3 2
1 4 3
1 5 4
5 0 2
Output
Case #1:3
Case #2:2
Case #3:-1

0 人解决,1 人已尝试。

0 份提交通过,共有 1 份提交。

9.9 EMB 奖励。

创建: 4 年,8 月前.

修改: 2 年,2 月前.

最后提交: 4 年,7 月前.

来源: 第四届程序设计竞赛

题目标签