#1629. BZOJ 3545. [ONTAK2010]Peaks

BZOJ 3545. [ONTAK2010]Peaks

题目描述

在 Bytemountains 有 nn 座山峰,每座山峰有他的高度 hih_i。有些山峰之间有双向道路相连,共 mm 条路径,每条路径有一个困难值,这个值越大表示越难走,现在有 qq 组询问,每组询问询问从点 vv 开始只经过困难值小于等于 xx 的路径所能到达的山峰中第 kk 高的山峰,如果无解输出 1-1

输入格式

第一行三个数 nnmmqq

第二行 nn 个数,第 ii 个数为 hih_i

接下来 mm 行,每行 33 个数 a b ca~b~c,表示从 aabb 有一条困难值为 cc 的双向路径。

接下来 qq 行,每行三个数 v x kv~x~k,表示一组询问。

输出格式

对于每组询问,输出一个整数表示答案。

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

提示

$n \le 10^5,~m,q \le 5 \times 10^5,~h_i,c,x \le 10^9$

题目来源

By Sbullet