← 返回题目
题库练习 [ABC143E] Travel by Car
← 上一题 下一题 →

A7573 | [ABC143E] Travel by Car

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的城镇，以及 $M$ 条道路。第 $i$ 条道路连接城镇 $A_i$ 和城镇 $B_i$，是双向的，道路长度为 $C_i$。

高桥君可以驾驶汽车在这些城镇之间通过道路移动。汽车的油箱容量为 $L$ 升，每行驶 $1$ 距离消耗 $1$ 升燃料。在途中到达某个城镇时，可以选择将油箱加满（也可以选择不加油）。不能在道路中途燃料耗尽。

请回答以下 $Q$ 个询问：

- 一开始，汽车油箱是满的。每个询问给定从城镇 $s_i$ 到城镇 $t_i$，请输出途中最少需要加油多少次才能到达。如果无法到达，请输出 $-1$。

输入格式

输入以如下格式从标准输入读入。

> $N$ $M$ $L$
> $A_1$ $B_1$ $C_1$
> $\vdots$
> $A_M$ $B_M$ $C_M$
> $Q$
> $s_1$ $t_1$
> $\vdots$
> $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
输入 #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
C++ 编辑器
输入
输出