AT_abc254_g [ABC254G] Elevators

题目描述

有一座由 $N$ 栋 $10^9$ 层高的楼组成的大楼群。每栋楼编号为 $1$ 到 $N$。

任意两栋不同的楼在相同的楼层之间通过连廊相连，可以在 $1$ 分钟内完成楼间移动。

此外，有 $M$ 部电梯。第 $i$ 部电梯连接第 $A_i$ 栋楼的 $B_i$ 层到 $C_i$ 层。使用这部电梯时，对于所有满足 $B_i \leq x, y \leq C_i$ 的整数对 $(x, y)$，可以在 $|x-y|$ 分钟内从第 $A_i$ 栋楼的 $x$ 层移动到 $y$ 层。

请回答以下 $Q$ 个询问。

• 判断是否可以从第 $X_i$ 栋楼的 $Y_i$ 层移动到第 $Z_i$ 栋楼的 $W_i$ 层，如果可以，输出所需的最短时间；否则输出 $-1$。

输入格式

输入通过标准输入按以下格式给出。

$N$ $M$ $Q$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_M$ $B_M$ $C_M$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

每个询问的格式如下：

$X_i$ $Y_i$ $Z_i$ $W_i$

输出格式

输出 $Q$ 行。第 $i$ 行对应第 $i$ 个询问，如果无法到达则输出 $-1$，否则输出最短移动时间。

输入输出样例 #1

输入 #1

3 4 3
1 2 10
2 3 7
3 9 14
3 1 3
1 3 3 14
3 1 2 7
1 100 1 101

输出 #1

12
7
-1

输入输出样例 #2

输入 #2

1 1 1
1 1 2
1 1 1 2

输出 #2

1

说明/提示

数据范围

• $1 \leq N, M, Q \leq 2 \times 10^5$
• $1 \leq A_i \leq N$
• $1 \leq B_i < C_i \leq 10^9$
• $1 \leq X_i, Z_i \leq N$
• $1 \leq Y_i, W_i \leq 10^9$
• 所有输入均为整数。

样例解释 1

对于第 $1$ 个询问，可以按如下方式在 $12$ 分钟内完成移动：

• 使用第 $1$ 部电梯，从第 $1$ 栋楼的 $3$ 层移动到 $9$ 层，耗时 $6$ 分钟。
• 在第 $9$ 层通过连廊从第 $1$ 栋楼移动到第 $3$ 栋楼，耗时 $1$ 分钟。
• 使用第 $3$ 部电梯，从第 $3$ 栋楼的 $9$ 层移动到 $14$ 层，耗时 $5$ 分钟。

对于第 $3$ 个询问，无法完成移动，因此输出 $-1$。

由 ChatGPT 4.1 翻译