AT_joi2024_yo2_e 高速道路の通行料金 (Highway Tolls)

JOI 王国是一个由 $N$ 个城市组成的王国，这些城市编号从 $1$ 到 $N$。JOI 王国内有 $M$ 条连接这些城市的**单向**高速公路，每条高速公路编号从 $1$ 到 $M$。通过第 $i$ ($1 \leq i \leq M$) 条高速公路，可以从城市 $A_i$ 前往城市 $B_i$，通过所需时间为 $L_i$。 每次通过高速公路时都需要支付通行费用。第 $i$ 条高速公路的基本通行费为 $C_i$，但由于 JOI 王国的工人都讨厌加班，距离某一基准时刻 $0$ 越远（无论是正还是负），通行费就会越高。具体来说，如果在时刻 $t$ 从城市 $A_i$ 出发，经过第 $i$ 条高速公路，则通行费用为 $C_i + K\times |t|$。其中 $K$ 为给定常数，$|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$ > $\vdots$ > $A_M$ $B_M$ $L_M$ $C_M$

如果无法通过高速公路从城市 $1$ 到达城市 $N$，请输出 `-1`。 如果可以达到，请输出最小的总通行费用。

## 小子任务 1.（9 分） $N \leq 100$，$M \leq 200$，$K = 0$。 2.（21 分） $N \leq 100$，$M \leq 200$，$L_i \leq 20$ （$1 \leq i \leq M$）。 3.（13 分） $N \leq 100$，$M = N - 1$，$A_i = i$，$B_i = i+1$ （$1 \leq i \leq M$）。 4.（23 分） $N \leq 100$，$M \leq 200$，且满足以下约束： - $N$ 为偶数，$\lfloor \frac{B_i}{2} \rfloor - \lfloor \frac{A_i}{2} \rfloor = 1$（$1 \leq i \leq M$）。其中 $\lfloor x \rfloor$ 为不超过 $x$ 的最大整数。 5.（16 分） $N \leq 100$，$M \leq 200$。 6.（11 分） $N \leq 1500$，$M \leq 3000$。 7.（7 分）无额外约束。 ## 样例说明 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$ 出发前往城市 $4$。通行费用 $3+0\times |3|=3$。 - 时刻 $8$：到达城市 $4$。 不存在能使总通行费用小于 $9$ 的其他方案，因此输出 $9$。 此输入满足小子任务 $1,2,5,6,7$ 的约束。 ## 样例说明 3 无法通过高速公路从城市 $1$ 到达城市 $2$，因此输出 `-1`。 该输入满足小子任务 $2,5,6,7$ 的约束。 ## 样例说明 4 该输入满足小子任务 $2,3,5,6,7$ 的约束。 ## 样例说明 5 存在多条连接相同 $(A_i,B_i)$ 对的道路。 该输入满足小子任务 $2,4,5,6,7$ 的约束。 ## 样例说明 6 该输入满足小子任务 $5,6,7$ 的约束。 # 数据范围与约束 - $2 \leq N \leq 4000$。 - $1 \leq M \leq 8000$。 - $0 \leq K \leq 100\,000$。 - $1 \leq A_i \leq N$（$1 \leq i \leq M$）。 - $1 \leq B_i \leq N$（$1 \leq i \leq M$）。 - $A_i \neq B_i$（$1 \leq i \leq M$）。 - $1 \leq L_i \leq 1\,000\,000$（$1 \leq i \leq M$）。 - $0 \leq C_i \leq 10^9$（$1 \leq i \leq M$）。 - 输入的所有数均为整数。 由 ChatGPT 5 翻译