Travel by Car

题目描述

有 $N$ 个城镇，编号为 $1$ 到 $N$，以及 $M$ 条道路。第 $i$ 条道路双向连接城镇 $A_i$ 和城镇 $B_i$，长度为 $C_i$。 Takahashi 将开车在这些城镇之间旅行，经过这些道路。汽车的油箱最多可以装 $L$ 升燃油，每行驶单位距离消耗一升燃油。在旅行过程中到达某个城镇时，他可以将油箱加满（也可以选择不加满）。如果某次行程会导致在道路中途油箱变空，则不能进行该次行程。 请处理以下 $Q$ 个询问：

现在油箱是满的。求从城镇 $s_i$ 到城镇 $t_i$ 旅行时最少需要加满油箱的次数。如果城镇 $t_i$ 无法到达，则输出 $-1$。

输入格式

输入从标准输入按以下格式给出： $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$。

3 2 5
1 2 3
2 3 3
2
3 2
1 3

0
1

4 0 1
1
2 1

-1

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

0
0
1
2
0
0
1
2
0
0
0
1
1
1
0
0
2
2
1
0

提示

输入中的所有数值均为整数。 $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$）从城镇 $3$ 到城镇 $2$ 的旅行中，我们可以使用第二条道路到达城镇 $2$，在此过程中无需加油。 从城镇 $1$ 到城镇 $3$ 的旅行中，我们可以先使用第一条道路到达城镇 $2$，加满油箱，然后使用第二条道路到达城镇 $3$。
可能没有任何道路。

标签: AtCoder|abc143E

来源

AtCoder|abc143E