题目详情题解（0）讨论（0）提交记录（0）

AT_joi2025ho_c.ミ・テレフェリコ (Mi Teleférico)

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

玻利维亚首都拉巴斯是著名的旅游胜地，其中的空中索道 Mi Teleférico 也很有名。你正在拉巴斯观光，并想尽可能多地游览景点。在本题中，我们考虑如下简化的情形。

拉巴斯共有 NN 个空中索道车站，按照海拔高度递增的顺序编号为 11 到 NN。共有 MM 条单向索道线路，编号为 11 到 MM。有 PP 个空中索道公司，编号为 11 到 PP。每条线路由一个公司管理。第 ii 条线路（1≤i≤M1 \leq i \leq M）从车站 AiA_i 通往车站 BiB_i，由公司 CiC_i 负责运营。注意，线路总是从低海拔车站开往高海拔车站，即 Ai<BiA_i < B_i 恒成立。

为了方便出行，拉巴斯交通局发售了不限次数的乘车通票。每张通票包含两个整数 l,rl, r，满足 1≤l≤r≤P1 \leq l \leq r \leq P。持有该通票的人可以乘坐任意由公司 l,l+1,…,rl, l+1, \dots, r 管理的线路。换句话说，对于 1≤i≤M1 \leq i \leq M，当 l≤Ci≤rl \leq C_i \leq r 时，持票人可以乘坐第 ii 条线路。每张通票可以用于多条符合条件的线路。我们记通票 (l,r)(l, r) 表示这种乘车通票。

现在有 QQ 位游客，编号为 11 到 QQ。第 jj 位游客持有通票 (Lj,Rj)(L_j, R_j) 并拥有 XjX_j 博利瓦诺现金。

每位游客的目标是，确保用自己目前拥有的通票，仅通过可乘坐的线路，从车站 11 出发，能够到达每一个车站。对于第 jj 位游客（1≤j≤Q1 \leq j \leq Q），可以按如下流程将手头的通票兑换一次，以达成目标：

  1. 他或她选择两个整数 l′,r′l', r'，使 1≤l′≤r′≤P1 \leq l' \leq r' \leq P。
  2. 以 ∣Lj−l′∣+∣Rj−r′∣|L_j - l'| + |R_j - r'| 博利瓦诺的手续费，将通票 (Lj,Rj)(L_j, R_j) 换为通票 (l′,r′)(l', r')。

请你判定对于每一位游客，能否在其手头现金范围内，实现从 11 号车站出发，使用可以乘坐的线路到达全部车站的目标。

编写程序，根据给定的车站、线路和游客信息，判断每位游客能否在规定现金内达成目标。

输入格式

从标准输入依次读取以下数据：

N M PN\ M\ P
A1 B1 C1A_1\ B_1\ C_1
A2 B2 C2A_2\ B_2\ C_2
⋮\vdots
AM BM CMA_M\ B_M\ C_M
QQ
L1 R1 X1L_1\ R_1\ X_1
L2 R2 X2L_2\ R_2\ X_2
⋮\vdots
LQ RQ XQL_Q\ R_Q\ X_Q

输出格式

向标准输出输出 QQ 行，第 jj 行（1≤j≤Q1 \leq j \leq Q）输出 Yes，如果第 jj 位游客可以实现目标，否则输出 No。

输入输出样例

  • 输入#1

    4 6 10
1 2 3
2 4 7
1 2 6
2 3 5
3 4 2
3 4 8
4
3 7 0
5 6 0
3 4 0
1 9 0

    输出#1

    Yes
No
No
Yes

  • 输入#2

    4 6 10
1 2 3
2 4 7
1 2 6
2 3 5
3 4 2
3 4 8
3
5 6 10
3 4 1
7 8 3

    输出#2

    Yes
No
Yes

  • 输入#3

    3 1 1000000000
1 2 6
1
1 1000000000 1000000000

    输出#3

    No

  • 输入#4

    5 9 2000
2 3 1814
2 3 457
1 2 1226
3 4 1354
1 5 1050
1 2 1725
2 3 1383
1 5 1626
1 4 1795
5
850 1872 128
82 428 1217
487 924 573
1639 1926 202
202 420 25

    输出#4

    Yes
Yes
Yes
Yes
No

说明/提示

子任务

1.（77 分）N≤50N \leq 50，M≤50M \leq 50，Q≤50Q \leq 50，并且 Xj=0X_j = 0（1≤j≤Q1 \leq j \leq Q）。
2.（88 分）P≤10P \leq 10。
3.（1111 分）P≤100P \leq 100。
4.（2323 分）P≤300 000P \leq 300\,000，Xj=0X_j = 0（1≤j≤Q1 \leq j \leq Q）。
5.（99 分）P≤300 000P \leq 300\,000。
6.（2222 分）N≤8 000N \leq 8\,000，M≤8 000M \leq 8\,000。
7.（2020 分）无额外限制。

样例解释 1

首先，第 11 位游客初始持有通票 (3,7)(3, 7) 和 00 博利瓦诺现金。他不需要换票即可达成目标。因为此票能乘坐下列四条线路：第 1,2,3,41, 2, 3, 4 条，并且可以按以下方式从车站 11 到达所有其它车站：

  • 通过线路 33 可达 1→21 \rightarrow 2。
  • 通过线路 1,41, 4 顺序可达 1→2→31 \rightarrow 2 \rightarrow 3。
  • 通过线路 3,23, 2 顺序可达 1→2→41 \rightarrow 2 \rightarrow 4。

因此，第 11 行输出 Yes。

接着，第 22 位游客初始持有通票 (5,6)(5, 6) 和 00 博利瓦诺现金。但此票只能乘坐第 3,43, 4 两条线路，无法从 11 号车站到达 44 号车站，也没有现金换票，因此输出 No。

同理，第 33 位游客无法达成目标，第 44 位游客可以达成目标。所以第 33 行输出 No，第 44 行输出 Yes。

该样例满足所有子任务的约束条件。

样例解释 2

车站和线路信息与样例输入 11 相同。

第 11 位游客初始持有通票 (5,6)(5, 6) 和 1010 博利瓦诺现金。他可以通过以下方式达成目标：

  1. 选择 l′=1,r′=5l' = 1, r' = 5。
  2. 花费 ∣5−1∣+∣6−5∣=5|5 - 1| + |6 - 5| = 5 博利瓦诺，将通票换为 (1,5)(1, 5)。

所以第 11 行输出 Yes。

第 22 位游客初始持有通票 (3,4)(3, 4) 和 11 博利瓦诺现金，无法通过任何换票方式达成目标。

第 33 位游客可以达成目标，因此第 33 行输出 Yes。

这样，该输入满足子任务 2,3,5,6,72, 3, 5, 6, 7 的约束。

样例解释 3

对于这些线路，不可能从 11 号车站到达 33 号车站，因此无论通票如何，游客都无法达成目的。

此样例满足子任务 6,76, 7 的约束。

样例解释 4

此样例满足子任务 5,6,75, 6, 7 的约束。

约束条件

  • 2≤N≤300 0002 \leq N \leq 300\,000。
  • 1≤M≤300 0001 \leq M \leq 300\,000。
  • 1≤P≤1091 \leq P \leq 10^9。
  • 1≤Ai<Bi≤N1 \leq A_i < B_i \leq N（1≤i≤M1 \leq i \leq M）。
  • 1≤Ci≤P1 \leq C_i \leq P（1≤i≤M1 \leq i \leq M）。
  • 1≤Q≤400 0001 \leq Q \leq 400\,000。
  • 1≤Lj≤Rj≤P1 \leq L_j \leq R_j \leq P（1≤j≤Q1 \leq j \leq Q）。
  • 0≤Xj≤1090 \leq X_j \leq 10^9（1≤j≤Q1 \leq j \leq Q）。
  • 所有输入数据均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页