P10538 [APIO2024] 星际列车
题目描述
**请勿使用 C++14 (GCC 9) 提交。**
在 2992 年，机器人已经取代了人类的大部分工作，大家都有着大量的空闲时间。因此你和家人决定利用这些时间来一场星际旅行。
有 $N$ 个人类已经可以到达的行星，编号为 $0$ 到 $N - 1$，以及 $M$ 种不同的星际列车路线。第 $i$ 种列车路线 ($0 \le i < M$) 在时间 $A[i]$ 从行星 $X[i]$ 出发，在时间 $B[i]$ 到达行星 $Y[i]$，票价为 $C[i]$。在行星之间，这些星际列车是仅有的交通方式。对于你搭乘的一列星际列车，你只能在它的终点站下车，并且你搭乘的下一趟列车的起点站必须和这趟列车的终点站相同（这里认为换乘不耗时）。形式化地，你可以依次乘坐第 $q[0], q[1], \ldots, q[P]$ 次列车，当且仅当对任意 $1 \le k \le P$ 都有 $Y[q[k - 1]] = X[q[k]]$，$B[q[k - 1]] \le A[q[k]]$。
在不同行星之间移动是非常耗时的，所以除了车票钱，餐费支出也不可忽视。列车上免费提供不限量的食物，也就是在列车上吃饭不花钱：如果你决定乘坐第 $i$ 种星际列车，则在任何 $A[i]$ 到 $B[i]$ 之间的时刻（包括端点）你都可以免费吃任意多顿饭。但如果你决定在行星 $i$ 吃饭，每顿饭都需要 $T[i]$ 元。
你和家人在旅途中总共需要吃 $W$ 顿饭，第 $i\ (0 \le i < W)$ 顿饭可以在 $L[i]$ 到 $R[i]$（包括端点）的任何时刻吃，吃饭不耗费时间。吃饭没有顺序要求，例如允许在吃完第 $1$ 顿饭后再吃第 $0$ 顿饭（见样例 $2$）。
现在是 $0$ 时刻，你和家人正在 $0$ 号行星上。你需要求出到达 $N - 1$ 号行星的最小花费，花费定义为车票价格和餐费之和。如果无法到达 $N - 1$ 号行星，最小花费定义为 $-1$。
### 实现细节
你无需在程序开头引入库 `train.h`。
你只需要实现以下函数：
```cpp
long long solve(int N, int M, int W, std::vector T,
std::vector X, std::vector Y,
std::vector A, std::vector B, std::vector C,
std::vector L, std::vector R);
```
+ $N$：行星数量。
+ $ M$：星际列车路线数量。
+ $W$：需要用餐的次数。
+ $T$：一个长度为 $N$ 的数组。$T[i]$ 表示在行星 $i$ 每次用餐的花费。
+ $X, Y, A, B, C$：五个长为 $M$ 的数组。$(X[i], Y[i], A[i], B[i], C[i])$ 描述了第 $i$ 条列车路线。
+ $L, R$：两个长为 $W$ 的数组。$(L[i], R[i])$ 描述了第 $i$ 顿饭的用餐时间。
+ 你需要返回从行星 $0$ 到达行星 $N - 1$ 的最小花费。如果行星 $N - 1$ 不可达，返回 $-1$。
+ 每个测试点中，该函数恰好被调用一次。
输入格式
评测程序示例读取如下格式的输入：
+ 第 $1$ 行：$N\ M\ W$
+ 第 $2$ 行：$T[0]\ T[1]\ T[2]\ \ldots\ T[N - 1]$
+ 第 $3 + i\ (0 \le i < M)$ 行：$X[i]\ Y[i]\ A[i]\ B[i]\ C[i]$
+ 第 $3 + M + i\ (0 \le i < W)$ 行：$L[i]\ R[i]$
输出格式
评测程序示例按照如下格式打印你的答案：
+ 第 $1$ 行：函数 `solve` 的返回值
说明/提示
### 样例解释
对于样例一，考虑如下调用：
```cpp
solve(3, 3, 1, {20, 30, 40}, {0, 1, 0}, {1, 2, 2},
{1, 20, 18}, {15, 30, 40}, {10, 5, 40}, {16}, {19});
```
一种可行的方案是依次乘坐第 $0, 1$ 次列车，花费为 $45$，具体流程如下：
| 时刻 | 你的行动 | 花费 |
| :---: | :---: | :---: |
| $1$ | 乘坐第 $0$ 次列车从 $0$ 号行星出发 | $10$ |
| $15$ | 到达 $1$ 号行星 | |
| $16$ | 在 $1$ 号行星吃第 $0$ 顿饭 | $30$ |
| $20$ | 乘坐第 $1$ 次列车从 $1$ 号行星出发 | $5$ |
| $30$ | 到达 $2$ 号行星 | |
一种更优的方案是乘坐第 $2$ 次列车，花费为 $40$，具体流程如下：
| 时刻 | 你的行动 | 花费 |
| :---: | :---: | :---: |
| $18$ | 乘坐第 $2$ 次列车从 $0$ 号行星出发 | $40$ |
| $19$ | 在第 $2$ 次列车上吃第 $0$ 顿饭 | |
| $40$ | 到达 $2$ 号行星 | |
在这种方案中，在时刻 $18$ 在第 $2$ 次列车上吃第 $0$ 顿饭也是合法的。
因此函数应该返回 $40$。
对于样例二，考虑如下调用：
```cpp
solve(3, 5, 6, {30, 38, 33}, {0, 1, 0, 0, 1}, {2, 0, 1, 2, 2},
{12, 48, 26, 6, 49}, {16, 50, 28, 7, 54}, {38, 6, 23, 94, 50},
{32, 14, 42, 37, 2, 4}, {36, 14, 45, 40, 5, 5});
```
最优解是：乘坐第 $0$ 次列车，车费为 $38$。在第 $0$ 次列车上免费吃第 $1$ 顿饭。第 $0, 2, 3$ 顿饭在行星 $2$ 上吃 ，花费 $33 \times 3 = 99$。 第 $4, 5$ 顿饭在行星 $0$ 上吃，花费 $30 \times 2 = 60$。总花费为 $38 + 99 + 60 = 197$。
因此函数应该返回 $197$。
### 数据范围
+ $2 \le N \le 10^5$
+ $0 \le M, W \le 10^5$
+ $0 \le X[i], Y [i] < N, X[i] \neq Y[i]$
+ $1 \le A[i] < B[i] \le 10^9$
+ $1 \le T[i], C[i] \le 10^9$
+ $1 \le L[i] \le R[i] \le 10^9$
详细子任务附加限制及分值如下表所示。
| 子任务编号 | 附加限制 | 分值 |
| :---: | :---: | :---: |
| $1$ | $N, M, A[i], B[i], L[i], R[i] \le 10^3, W \le 10$ | $5$ |
| $2$ | $W = 0$ | $5$
| $3$ | 每顿饭的用餐时间两两不交。形式化地，对于任何时刻 $z$ 满足 $1 \le z \le 10^9$，至多存在一个 $i\ (0 \le i < W)$ 使得 $L[i] \le z \le R[i]$。 | $30$ |
| $4$ | 没有额外的约束条件 | $60$ |