文理学院程序设计在线练习


坚持散步

Time Limit: 3 Second(s)    Memory Limit: 32 MB

Total Submission(s): 161   Accepted Submission(s): 94
Problem Description

住在南山校区的HY喜欢散步。他发现南山校区有n个景点(从1到n进行编号)很值得观赏,比如竹林舞步,小河夕阳等。这些景点中,有些相互能够直达,而有些要先经过其他的一些景点才能到达。他已经记下了一些直达道路的用时信息。散步是好的,但散步太久也会累的,所以当他身处某个景点时,就想知道从这个景点散步到另一个他想去的景点的最少用时。

Input

测试数据有多组,首先输入一个整数T(0<T<=20),表示测试组数。然后有T组测试数据。
每组测试包含两个部分。分别是: 景点信息 查询

景点信息 部分,首先是2个整数n和m(2<=n<=100,1<=m<=n(n-1)/2),分别表示有n个景点,以及m条直达道路的用时信息。然后有m行输入,每行输入三个整数a,b,c(1<=a,b<=n,a<>b,1<=c<100),表示由景点a散步到景点b,HY散步需要用时c分钟,当然,他由景点b散步到景点a也要c分钟。

查询 部分,首先是1个整数k(1<=k<=5000),表示后面接k次询问。紧接着k行数据,每行包括两个整数s,d(1<=s,d<=n,s<>d),分别表示HY想知道从景点s散步到另一个景点d的用时(分钟数)。

注意,因为HY有点粗心,可能发生以下情况:
(1)他所记下有些用时信息可能重复,比如:
1 2 3
2 1 3
(2)有些同一条路的用时信息可能不一致,比如:
1 2 3
1 2 4
在这种情况下,以其中用时最少的信息为准。
(3)有些路用时信息可能忘记了,比如有3个景点1,2,3;他只记住1条路的用时:
1 2 1
在这种情况下,我们认为从景点1到景点3没有直达的路,从景点2到景点3也没有直达的路。

Output

对于每次询问,按行输出,从景点s散步到另一个景点d的最少用时,如果景点s到景点d无路可通,输出-1。

Sample Input
2
3 2
1 2 3
2 3 1
3
1 2
1 3
3 2
3 2
1 2 3
2 1 2
3
1 2
1 3
2 3
Sample Output
3
4
1
2
-1
-1
Hint

输入数据较多,用 scanf / printf 进行读入/输出,效率会更高

Author

hlj

Source

zscas第三届程序设计竞赛