#P3545. [ONTAK2010]Peaks

    ID: 2755 传统题 2500ms 128MiB 尝试: 3880 已通过: 601 难度: 7 上传者: 标签>难度分类提高+/省选-图论Kruskal 重构树数据结构普通并查集树算法树上倍增子树转区间排序与序列处理离散化可持久化线段树路径复制前缀版本作差CF2300

[ONTAK2010]Peaks

[ONTAK2010] Peaks

题目描述

山地中有编号为 11 到 nn 的山峰,第 ii 座山峰的高度为 hih_i。山峰之间有 mm 条双向道路,每条道路都有一个困难值。

每次询问给出 v,x,kv,x,k。从山峰 vv 出发,只走困难值不超过 xx 的道路。将所有能到达的山峰(包括 vv)按高度从高到低排列,求第 kk 座山峰的高度。高度相同的山峰分别占一个名次。可到达的山峰不足 kk 座时,输出 −1-1。

输入格式

第一行三个整数 n,m,qn,m,q,分别表示山峰数、道路数和询问数。第二行给出 nn 个整数 h1,…,hnh_1,\ldots,h_n。

接下来 mm 行,每行三个整数 a,b,ca,b,c,表示山峰 a,ba,b 之间有一条困难值为 cc 的双向道路。

最后 qq 行,每行三个整数 v,x,kv,x,k,表示一次询问。直接使用输入给出的参数。

输出格式

每个询问输出一行,表示第 kk 高的山峰的高度;不存在时输出 −1-1。

样例 #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

数据范围

1≤n≤1051\le n\le10^5,0≤m,q≤5×1050\le m,q\le5\times10^5,0≤hi,c,x≤1090\le h_i,c,x\le10^9。道路端点和起点均为有效山峰编号,kk 为正整数。