[Jeremy Wu]冒险之路,平凡之路

Time Limit
1s
Memory Limit
32768KB
Judge Program
Standard
Ratio(Solve/Submit)
32.55%(167/513)
Description:

夜煞NightFury)是出自《驯龙高手2》中非常稀有且最危险聪明的龙,与其它龙的造型很不一样,类似蝙蝠,同时融合了猫科动物的体型以及野狼般精锐的眼神,身体附有黑色鳞片。体积娇小,表情动作灵巧可爱,双翼比例是龙里最大。翼面多达三对,因此飞行时间更长,速度更快更灵活。与其他龙所喷发的火焰不同,是伴随着电石气与氧气的幽蓝色球,在冲击或飞行一段距离后爆炸,攻击精准,格斗技能高超,高度智慧、体型较小、飞行和攻击能力优越。

现在,身为年轻英勇的维京勇士小嗝嗝的你,拥有一只叫没牙仔的夜煞。为了改变德雷格屠龙的观念,你们正在追赶嗜权的德雷格的路上。狡猾的德雷格躲在某个不知名的地方,但是聪明的你,利用手中的地图可以得某些地点之间的距离,也从他人口中得知了德雷格躲藏的地方。

现在已知没牙仔的飞行轨迹,博克岛的村民们非常想知道你和没牙仔在冒险过程中走过的总路程(同一段路线无须重复计算,但可能重复走)。如果在飞行轨迹途中遇到了德雷格,你会立马前往与德雷格见面,飞行结束。

Input:

有多组数据测试,以输入00结束。

对于每组输入数据,首先输入nt,表示有n个地点(n< 2000)。然后接下来有t行输入,每行输入abvalue表示a地点距离b地点value的长度,没有表明关系的地点不存在路,如果同一段路第二次输入的长度比先前的短,则ab点间距离取短的那条。然后输入we,表示接下来有w行输入和德雷格所在的e点,每行输入cd表示没牙仔从c地点飞到d地点,且一定是相邻的两点,先后关系表示没牙仔先后经过的地点,保证不会经过不存在的路。

Output:

对于每组测试,输出“Case#k: ”,首先,k1开始标号。

输出没牙仔在冒险过程中走过的总路程


Sample Input:
7 8
1 2 3
2 3 4
3 4 5
4 5 6
4 5 1
5 6 3
5 6 4
6 8 1
6 8
1 2
2 3
3 4
4 5
5 6
6 8
5 4
1 2 3
2 3 4
3 4 10
4 5 15
11 4
1 2
2 1
1 2
2 3
3 2
2 1
1 2
2 3
3 4
4 5
5 6
0 0
Sample Output:
Case #1: 17
Case #2: 17
Source:

Jeremy Wu


Submit