33OJ
登录 注册

#P17757. 「RSOI-3F」信号传递 / signal

「RSOI-3F」信号传递 / signal

背景

题目来源:【HT-126-Div.2】核桃 CSP-S 组模拟赛

题目描述

给定 nn 个节点,每个节点有两个正整数权值 AiA_i 和 PiP_i。

在图上,从节点 uu 可以向节点 vv(u≠vu \neq v)发送信号,当且仅当这两个节点的权值满足以下条件:

Av mod Au≤PuA_v \bmod A_u \le P_u

现在给定起点 SS 和终点 TT,请你求出信号从 SS 传递到 TT 的最短路径长度(即最少经过的边数)。如果无法将信号传递到 TT,请输出 -1。

输入格式

第一行包含三个正整数 n,S,Tn, S, T,分别表示节点总数、起点编号和终点编号。

接下来 nn 行,每行包含两个非负整数 Ai,PiA_i, P_i,表示第 ii 个节点的权值。

输出格式

输出一行一个整数,表示最短路径的长度。如果无法到达,输出 -1。

6 1 4
3 0
9 1
19 2
38 0
6 0
18 0
3

提示

【样例解释 #1】

  • 节点 1 的权值为 A1=3,P1=0A_1=3, P_1=0。可以到达满足 Av mod 3≤0A_v \bmod 3 \le 0 的节点,即节点 2(9 mod 3=09 \bmod 3 = 0)、节点 5(6 mod 3=06 \bmod 3 = 0)和节点 6。
  • 节点 2 的权值为 A2=9,P2=1A_2=9, P_2=1。可以到达满足 Av mod 9≤1A_v \bmod 9 \le 1 的节点,即节点 3(19 mod 9=1≤119 \bmod 9 = 1 \le 1)和节点 6。
  • 节点 3 的权值为 A3=19,P3=2A_3=19, P_3=2。可以到达满足 Av mod 19≤2A_v \bmod 19 \le 2 的节点,即节点 4(38 mod 19=0≤238 \bmod 19 = 0 \le 2)。
  • 最短路径为 1→2→3→41 \to 2 \to 3 \to 4,经过了 3 条边,因此长度为 3。虽然节点 1 可以直接到节点 5 或 6,但它们无法进一步到达终点 4。

【数据范围】

本题采用捆绑测试。

对于所有测试数据,保证: 1≤n,Ai,Pi≤106,1≤S,T≤n1 \le n,A_i,P_i \le 10^6, 1 \le S, T \le n。

Subtask 编号 n≤n\le Ai≤A_i\le 特殊性质 分值
1 30003000 500500 无 2020
2 10510^5 ^ 1515
3 ^ 10510^5 保证 Pi=0P_i=0
4 ^ Pi≤2P_i\le 2 1010
5 无
6 10610^6 ^ 3030