背景
题目来源:【HT-126-Div.2】核桃 CSP-S 组模拟赛
题目描述
给定 n 个节点,每个节点有两个正整数权值 Ai 和 Pi。
在图上,从节点 u 可以向节点 v(u=v)发送信号,当且仅当这两个节点的权值满足以下条件:
AvmodAu≤Pu
现在给定起点 S 和终点 T,请你求出信号从 S 传递到 T 的最短路径长度(即最少经过的边数)。如果无法将信号传递到 T,请输出 -1。
输入格式
第一行包含三个正整数 n,S,T,分别表示节点总数、起点编号和终点编号。
接下来 n 行,每行包含两个非负整数 Ai,Pi,表示第 i 个节点的权值。
输出格式
输出一行一个整数,表示最短路径的长度。如果无法到达,输出 -1。
6 1 4
3 0
9 1
19 2
38 0
6 0
18 0
3
提示
【样例解释 #1】
- 节点 1 的权值为 A1=3,P1=0。可以到达满足 Avmod3≤0 的节点,即节点 2(9mod3=0)、节点 5(6mod3=0)和节点 6。
- 节点 2 的权值为 A2=9,P2=1。可以到达满足 Avmod9≤1 的节点,即节点 3(19mod9=1≤1)和节点 6。
- 节点 3 的权值为 A3=19,P3=2。可以到达满足 Avmod19≤2 的节点,即节点 4(38mod19=0≤2)。
- 最短路径为 1→2→3→4,经过了 3 条边,因此长度为 3。虽然节点 1 可以直接到节点 5 或 6,但它们无法进一步到达终点 4。
【数据范围】
本题采用捆绑测试。
对于所有测试数据,保证: 1≤n,Ai,Pi≤106,1≤S,T≤n。
| Subtask 编号 |
n≤ |
Ai≤ |
特殊性质 |
分值 |
| 1 |
3000 |
500 |
无 |
20 |
| 2 |
105 |
^ |
15 |
| 3 |
^ |
105 |
保证 Pi=0 |
| 4 |
^ |
Pi≤2 |
10 |
| 5 |
无 |
| 6 |
106 |
^ |
30 |