#C. bzoj3551 [ONTAK2010] Peaks

Type: Default

2000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在 Bytemountains 有 $n$ 座山峰，每座山峰有他的高度 $h_{i}$ 。有些山峰之间有双向道路相连，共 $m$ 条路径，每条路径有一个困难值，这个值越大表示越难走，现在有 $q$ 组询问，每组询问询问从点 $v$ 开始只经过困难值小于等于 $x$ 的路径所能到达的山峰中第 $k$ 高的山峰，如果无解输出 $- 1$ 。

输入格式

第一行三个数 $n$ ， $m$ ， $q$ 。

第二行 $n$ 个数，第 $i$ 个数为 $h_{i}$ 。

接下来 $m$ 行，每行 $3$ 个数 $a b c$ ，表示从 $a$ 到 $b$ 有一条困难值为 $c$ 的双向路径。

接下来 $q$ 行，每行三个数 $v x k$ ，表示一组询问。

输出格式

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

输入数据 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

输出数据 1

提示

$n \leq 1 0^{5}, m, q \leq 5 \times 1 0^{5}, h_{i}, c, x \leq 1 0^{9}$

题目来源

By Sbullet

并查集与Kruskal重构树

Not Attended

Status: Done
Rule: IOI
Problem: 13
Start at: 2024-8-21 7:00
End at: 2024-8-27 7:00
Duration: 144 hour(s)
Host: 梁泽贤 (liangzexian)
Partic.: 11

#C. bzoj3551 [ONTAK2010] Peaks

bzoj3551 [ONTAK2010] Peaks

题目描述

输入格式

输出格式

提示

题目来源

并查集与Kruskal重构树

Status

Development

Support

#C. bzoj3551 [ONTAK2010] Peaks

bzoj3551 [ONTAK2010] Peaks

题目描述

输入格式

输出格式

输入数据 1

输出数据 1

提示

题目来源

并查集与Kruskal重构树

Status

Development

Support

Don't have an account?

SIGN IN