主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 J: V8与女友

问题 J: V8与女友

时间限制: 1 Sec  内存限制: 128 MB
提交: 1249  解决: 259
[提交][状态][讨论版]

题目描述

那是遥远的公元前2333年,V8还有女朋友的时代。

他和他的女友分别是两个距离遥远的部落的首领,那时候没有现在发达的交通工具和路网,V8每次希望团圆的时候,都要跋山涉水不远万里去会见他的爱人,辛酸的很。经过很多次的旅途,V8掌握了他可以走的所有的路的路线图,毕竟作为首领,不能离开自己的领地太久,所以V8希望你给他找出一条最近的路,并且输出一次往返所需要的最短时间,V8并不会在对方领地停留,说个你好就回来了,需要的时间为0。

虽然不管你求出来有多快,最终V8还是觉得自己在路上花费的时间太多,选择了舍小家而为大家(手动滑稽。

输入

第一行一个正整数t,表示数据的组数(t <=10)。

之后对于每组数据,第一行一个正整数k,表示这个地图(无向图)的路径数(k<=10000)。

之后有k行,每一行三个正整数,s,t,v。表示路的两个端点和这条路需要的时间(s,t,v <=100)。

第k+1行为两个数,v,m,表示V8和他爱人的所在地。

输出

对于每组数据,输出一行一个正整数,为V8一个来回最短的时间(数据保证有通路)。

样例输入

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

样例输出

4

提示

[提交][状态][讨论版]