迷宫探索

题目描述:

爱丽丝正在探索一个危险的大型迷宫。该迷宫包含\(n\)个洞穴（编号从1到\(n\)）和\(m\)条单向通道连接这些洞穴（通道中的陷阱使得通过后难以返回）。每条通道表示为\((u,v,d)\)，其中\(u\)是起点洞穴，\(v\)是终点洞穴，\(d\)是通道难度值。整个系统可视为带权有向图。

爱丽丝初始具有\(x\)点体力值。当通过难度为\(d\)的通道时，体力值变为\(\lfloor \frac{x}{d} \rfloor\)。当体力值降为0时无法继续探索。

由于爱丽丝方向感差，她提出\(Q\)个问题：若从洞穴\(p_i\)出发，初始体力\(x_i\)，每次随机选择可用通道，求体力耗尽前必须经过的最少通道数。（重复通过通道仍会消耗体力）

输入格式:

第一行三个整数\(n,m,Q\) (\(1\le n,Q \le 2\times 10^5, n\le m \le 5\times 10^5\))
接下来\(m\)行，每行三个整数\(u,v,d\) (\(1\le u, v \le n, 2\le d \le 10^9\))表示通道  
最后\(Q\)行，每行两个整数\(p_i,x_i\) (\(1\le p_i \le n, 1\le x_i \le 10^9\))表示查询

输出格式:

输出若干行，每行一个整数表示对应查询的答案，如果不能体力值降为0不输出。

数据范围:

测试点编号	n≤	m≤	Q≤	特殊性质
1∼6	100	200	100	无
7∼12	5000	10000	5000	无
13∼14	5000	10000	5000	有
15∼20	2×105	5×105	2×105	无

特殊性质：所有通道的d都为10⁹。

样例输入:

3 4 7
1 2 2
2 3 4
3 2 3
3 3 2
1 10
2 9
3 2
2 8
3 1
1 7
2 4

样例输出:

3
2
1
2
1
2
2

时间限制: 4000ms
空间限制: 256MB

---

来源: 25年比赛初中组t5