#P3545. [ONTAK2010]Peaks
[ONTAK2010]Peaks
[ONTAK2010] Peaks
题目描述
山地中有编号为 到 的山峰,第 座山峰的高度为 。山峰之间有 条双向道路,每条道路都有一个困难值。
每次询问给出 。从山峰 出发,只走困难值不超过 的道路。将所有能到达的山峰(包括 )按高度从高到低排列,求第 座山峰的高度。高度相同的山峰分别占一个名次。可到达的山峰不足 座时,输出 。
输入格式
第一行三个整数 ,分别表示山峰数、道路数和询问数。第二行给出 个整数 。
接下来 行,每行三个整数 ,表示山峰 之间有一条困难值为 的双向道路。
最后 行,每行三个整数 ,表示一次询问。直接使用输入给出的参数。
输出格式
每个询问输出一行,表示第 高的山峰的高度;不存在时输出 。
样例 #1
10 11 4
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
1 5 2
1 5 6
1 5 8
8 9 2
6
1
-1
8
数据范围
,,。道路端点和起点均为有效山峰编号, 为正整数。
相关
在下列比赛中: