#214411. [JOI2024 预选赛 R2] 高速公路通行费 / Highway Tolls

JOI 王国由 个城市组成，这些城市被编号为 至 。JOI 王国内有 条单向高速公路，这些高速公路被编号为 至 。通过高速公路 （），可以从城市 移动到城市 ，所需时间为 。

每次通过高速公路都会产生通行费。高速公路 的基本通行费为 ，但由于 JOI 王国的劳动者厌恶加班，若离开基准时刻 的时间越久，通行费就会越高。具体而言，若在时刻 从城市 出发并通过高速公路 ，则通行费可表示为 ，其中 表示 的绝对值。

你居住在城市 ，计划前往朋友居住的城市 。你希望确认是否可能通过高速公路从城市 移动到城市 ，若可能，则进一步求出通行费总和的最小值。你可以自由选择移动路径和在各城市出发的时间。特别地，允许在负时刻从城市 出发，也允许在途中某个城市停留一段时间。

给定高速公路的信息以及常数 ，请编写一个程序，判断是否可以通过高速公路从城市 移动到城市 ，若可以，则求出通行费总和的最小值。

此外，在本题的约束条件下，若可以通过高速公路从城市 移动到城市 ，则通行费总和的最小值必定为整数。

输入以如下格式给出：

若无法通过高速公路从城市 移动到城市 ，则输出 。若可以，则输出一行整数，表示通行费总和的最小值。

样例输入 1

4 4 2
1 2 3 2
1 3 1 10
2 3 1 4
3 4 5 3

样例输出 1

15

样例输入 2

4 4 0
1 2 3 2
1 3 1 10
2 3 1 4
3 4 5 3

样例输出 2

9

样例输入 3

2 1 10
2 1 4 7

样例输出 3

-1

样例输入 4

4 3 5
1 2 3 1
2 3 1 10
3 4 7 6

样例输出 4

37

样例输入 5

8 8 2
1 2 1 5
5 6 3 1
2 4 10 18
3 5 3 1
1 3 4 2
5 6 2 2
2 5 2 3
6 8 1 1

样例输出 5

25

样例输入 6

6 10 100000
4 2 212037 752027141
2 5 667097 1571491
2 1 769275 576006950
1 2 711969 526189398
5 3 733555 206320177
3 4 364807 802102091
1 4 467240 183184247
3 5 44994 15991843
5 3 613192 782356546
4 6 832593 639529758

样例输出 6

47546714005

样例 1 解释

JOI 王国的城市与道路示意图如下所示。圆圈代表城市，箭头代表道路，每条道路旁标注了其对应的 和 的值（按此顺序）。圆圈内标注的数字代表该城市的编号。

:::align{center} :::

按以下方式移动时，通行费总和为 15：

• 时刻 ：从城市 1 出发，前往城市 3，通行费为 。
• 时刻 ：到达城市 3，立即前往城市 4，通行费为 。
• 时刻 ：到达城市 4。

不存在通行费总和小于 15 的移动方案，因此输出 15。

该输入样例满足子任务 2、5、6、7 的约束。

样例 2 解释

本样例与样例 1 仅在 的取值上不同。

按以下方式移动时，通行费总和为 9：

• 时刻 ：从城市 1 出发，前往城市 2，通行费为 。
• 时刻 ：到达城市 2，立即前往城市 3，通行费为 。
• 时刻 ：到达城市 3，停留于城市 3。
• 时刻 ：从城市 3 出发，前往城市 4，通行费为 。
• 时刻 ：到达城市 4。

不存在通行费总和小于 9 的移动方案，因此输出 9。

该输入样例满足子任务 1、2、5、6、7 的约束。

样例 3 解释

无法通过高速公路从城市 1 移动到城市 2，因此输出 。

该输入样例满足子任务 2、5、6、7 的约束。

样例 5 解释

可能存在多个具有相同 对的道路。

该输入样例满足子任务 2、4、5、6、7 的约束。

数据范围

• 。
• 。
• 。
• （）。
• （）。
• （）。
• （）。
• （）。
• 所有输入的值均为整数。

子任务

1. （9 分），，。
2. （21 分），，（）。
3. （13 分），，，（）。
4. （23 分），，并满足以下约束：
   • 为偶数，且对所有 ，满足 。其中， 表示不超过 的最大整数。
5. （16 分），。
6. （11 分），。
7. （7 分）无额外约束。

翻译由 Qwen3-235B 完成。