分数: 500 点
问题陈述
有 N 城镇编号 1 to N 和 M 道路。的 i第条路连接城镇 A_i 和镇 B_i 双向且长度为 C_i.
高桥将驾车在这些城镇之间行驶,并经过这些道路。他的车的油箱最多可以装 L 升燃油,每行驶单位距离消耗一升燃油。当旅行时访问一个城镇时,他可以加满油箱(或选择不这样做)。导致油箱在半路上变空的旅行是不能进行的。
处理以下内容 Q 查询:
- 水箱现已满。找出他从城镇出发时需要加满油箱的最少次数 s_i 到镇 t_i。如果镇 t_i 无法访问,打印 -1.
约束
- 输入中的所有值都是整数。
- 2 \leq N \leq 300
- 0 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq L \leq 10^9
- 1 \leq A_i, B_i \leq N
- A_i \neq B_i
- \left(A_i, B_i\right) \neq \left(A_j, B_j\right) (如果 i \neq j)
- \left(A_i, B_i\right) \neq \left(B_j, A_j\right) (如果 i \neq j)
- 1 \leq C_i \leq 10^9
- 1 \leq Q \leq N\left(N-1\right)
- 1 \leq s_i, t_i \leq N
- s_i \neq t_i
- \left(s_i, t_i\right) \neq \left(s_j, t_j\right) (如果 i \neq j)
输入
输入由标准输入按以下格式给出:
N M L A_1 B_1 C_1 : A_M B_M C_M Q s_1 t_1 : s_Q t_Q
输出
打印 Q 行。
的 i- 第行应包含从城镇出发时需要加满油箱的最少次数 s_i 到镇 t_i。如果镇 t_i 无法访问,该行应包含 -1 代替。
示例输入 1
3 2 5 1 2 3 2 3 3 2 3 2 1 3
示例输出 1
0 1
从城镇出发 3 到镇 2,我们可以走第二条路到达城镇 2 途中无需给油箱加油。
从城镇出发 1 到镇 3,我们可以先走第一条路去城镇 2,加满油箱,然后使用第二条路到达城镇 3.
示例输入 2
4 0 1 1 2 1
示例输出 2
-1
可能根本就没有路。
示例输入 3
5 4 4 1 2 2 2 3 2 3 4 3 4 5 2 20 2 1 3 1 4 1 5 1 1 2 3 2 4 2 5 2 1 3 2 3 4 3 5 3 1 4 2 4 3 4 5 4 1 5 2 5 3 5 4 5
示例输出 3
0 0 1 2 0 0 1 2 0 0 0 1 1 1 0 0 2 2 1 0