← 返回题目列表

AtCoder · abc143_e

E. 驾车旅行

中文机器翻译题面 查看原题

分数: 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