第 3 题高速公路通行费 (`highwaytolls`)

CSP-S 复赛模拟赛 21 · 时间限制 1.0 s · 空间限制 256 MB · 89 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 highwaytolls.in，输出文件 highwaytolls.out。

题目描述

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

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

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

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

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

输入格式

输入以如下格式给出：

N M K
A_1 B_1 L_1 C_1
A_2 B_2 L_2 C_2
...
A_M B_M L_M C_M

输出格式

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

样例

样例 1

输入：

输出：

样例 2

输入：

输出：

样例 3

输入：

2 1 10
2 1 4 7

输出：

-1

样例 4

输入：

输出：

样例 5

输入：

输出：

样例 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

输出：

47546714005

提示

样例 1 解释

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

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

时刻 $-1$ ：从城市 1 出发，前往城市 3，通行费为 $10 + 2 \times |-1| = 12$ 。
时刻 0：到达城市 3，立即前往城市 4，通行费为 $3 + 2 \times |0| = 3$ 。
时刻 5：到达城市 4。

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

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

样例 2 解释

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

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

时刻 $-3$ ：从城市 1 出发，前往城市 2，通行费为 $2 + 0 \times |-3| = 2$ 。
时刻 0：到达城市 2，立即前往城市 3，通行费为 $4 + 0 \times |0| = 4$ 。
时刻 1：到达城市 3，停留于城市 3。
时刻 3：从城市 3 出发，前往城市 4，通行费为 $3 + 0 \times |3| = 3$ 。
时刻 8：到达城市 4。

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

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

样例 3 解释

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