P14128 [SCCPC 2021] Spicy Restaurant

成都有 $n$ 家火锅店，编号从 $1$ 到 $n$，第 $i$ 家火锅店的火锅辣度为 $w_i$。辣度越高越辣，辣度较低则更温和（当然还是要小心辣）。 我们可以把这 $n$ 家火锅店看作无向图中的 $n$ 个节点，图上有 $m$ 条边。现在有 $q$ 位游客想要尝试火锅。给定游客当前所在的火锅店以及他们能承受的最大辣度，请你计算每位游客距离他能够接受的最近火锅店的最短距离。 在本题中，路径的距离定义为路径上边的数量。

每个测试文件只有一组测试数据。 第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n, m \le 10^5, 1 \le q \le 5 \times 10^5$），分别表示火锅店的数量、边的数量和游客的数量。 第二行包含 $n$ 个整数 $w_1, w_2, \cdots, w_n$（$1 \le w_i \le 100$），其中 $w_i$ 表示第 $i$ 家火锅店的辣度。 接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n, u_i \ne v_i$），表示有一条连接火锅店 $u_i$ 与 $v_i$ 的无向边。 接下来的 $q$ 行，每行包含两个整数 $p_i$ 和 $a_i$（$1 \le p_i \le n, 1 \le a_i \le 100$），表示第 $i$ 位游客当前所处的火锅店是 $p_i$，他所能承受的最大辣度为 $a_i$。

输出 $q$ 行，其中第 $i$ 行输出一个整数，表示第 $i$ 位游客距离他能够接受的最近火锅店的最短距离。如果不存在这样的一家火锅店，输出 $-1$。

由 ChatGPT 5 翻译