#P11664. [JOI 2025 Final] 缆车 / Mi Teleférico
[JOI 2025 Final] 缆车 / Mi Teleférico
题目背景
译自 第24回日本情報オリンピック 本選 T3。
Mi Teleférico 指的是连接玻利维亚拉巴斯市(La Paz)及埃尔阿尔托市(El Alto)的缆车系统。
题目描述
给定一张 个点 条边的有向无环图。这张有向图的边是由 个公司(编号 )修建的,每条边恰好被一个公司修建。
节点标号 ,第 ()条边由节点 指向节点 ,且是公司 修建的。这里,保证 。
有 个询问,每个询问给定区间 ()和钱数 。目标是从 号点只经过编号 的公司修建的边,可以到达其他任意一个节点。
为此,可以选择一个新的区间 (),将 变为 。这会花费 的代价,这个操作至多只能执行一次。操作的代价必须不大于钱数 。
对于每个询问,判断是否能够达成目标。
输入格式
如下所示:
输出格式
对于第 个询问,如果可以达成,输出一行一个 ;否则输出一行一个 。
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
Yes
No
No
Yes
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
Yes
No
Yes
3 1 1000000000
1 2 6
1
1 1000000000 1000000000
No
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
Yes
Yes
Yes
Yes
No
提示
样例解释
样例 解释
第 个询问中, 已经可以满足条件,无需进行操作。
第 个询问中, 不满足条件,然后无法进行任何操作,所以无法达成目标。
该样例满足所有子任务的限制。
样例 解释
第 个询问中,选择 ,花费 的代价可以达成目标。
该样例满足子任务 的限制。
样例 解释
该样例满足子任务 的限制。
样例 解释
该样例满足子任务 的限制。
数据范围
- 。
- 。
- 。
- ()。
- ()。
- 。
- ()。
- ()。
- 输入的都是整数。
子任务
- (7pts),()。
- (8pts)。
- (11pts)。
- (23pts),()。
- (9pts)。
- (22pts)。
- (20pts)无额外限制。