{"problem":{"name":"[APIO2024] 星际列车","description":{"content":"**请勿使用 C++14 (GCC 9) 提交。** 在 2992 年，机器人已经取代了人类的大部分工作，大家都有着大量的空闲时间。因此你和家人决定利用这些时间来一场星际旅行。 有 $N$ 个人类已经可以到达的行星，编号为 $0$ 到 $N - 1$，以及 $M$ 种不同的星际列车路线。第 $i$ 种列车路线 ($0 \\le i < M$) 在时间 $A[i]$ 从行星 $X[i]$ 出发，在","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1024000},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10538"},"statements":[{"statement_type":"Markdown","content":"**请勿使用 C++14 (GCC 9) 提交。**\n\n在 2992 年，机器人已经取代了人类的大部分工作，大家都有着大量的空闲时间。因此你和家人决定利用这些时间来一场星际旅行。\n\n有 $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]]$。\n\n在不同行星之间移动是非常耗时的，所以除了车票钱，餐费支出也不可忽视。列车上免费提供不限量的食物，也就是在列车上吃饭不花钱：如果你决定乘坐第 $i$ 种星际列车，则在任何 $A[i]$ 到 $B[i]$ 之间的时刻（包括端点）你都可以免费吃任意多顿饭。但如果你决定在行星 $i$ 吃饭，每顿饭都需要 $T[i]$ 元。\n\n你和家人在旅途中总共需要吃 $W$ 顿饭，第 $i\\ (0 \\le i < W)$ 顿饭可以在 $L[i]$ 到 $R[i]$（包括端点）的任何时刻吃，吃饭不耗费时间。吃饭没有顺序要求，例如允许在吃完第 $1$ 顿饭后再吃第 $0$ 顿饭（见样例 $2$）。\n\n现在是 $0$ 时刻，你和家人正在 $0$ 号行星上。你需要求出到达 $N - 1$ 号行星的最小花费，花费定义为车票价格和餐费之和。如果无法到达 $N - 1$ 号行星，最小花费定义为 $-1$。\n\n### 实现细节\n\n你无需在程序开头引入库 `train.h`。\n\n你只需要实现以下函数：\n\n```cpp\nlong long solve(int N, int M, int W, std::vector<int> T,\n                std::vector<int> X, std::vector<int> Y,\n                std::vector<int> A, std::vector<int> B, std::vector<int> C,\n                std::vector<int> L, std::vector<int> R);\n```\n\n+   $N$：行星数量。\n+  $ M$：星际列车路线数量。\n+   $W$：需要用餐的次数。\n+   $T$：一个长度为 $N$ 的数组。$T[i]$ 表示在行星 $i$ 每次用餐的花费。\n+   $X, Y, A, B, C$：五个长为 $M$ 的数组。$(X[i], Y[i], A[i], B[i], C[i])$ 描述了第 $i$ 条列车路线。\n+   $L, R$：两个长为 $W$ 的数组。$(L[i], R[i])$ 描述了第 $i$ 顿饭的用餐时间。\n+   你需要返回从行星 $0$ 到达行星 $N - 1$ 的最小花费。如果行星 $N - 1$ 不可达，返回 $-1$。\n+   每个测试点中，该函数恰好被调用一次。\n\n## Input\n\n评测程序示例读取如下格式的输入：\n\n+   第 $1$ 行：$N\\ M\\ W$\n+   第 $2$ 行：$T[0]\\ T[1]\\ T[2]\\ \\ldots\\ T[N - 1]$\n+   第 $3 + i\\ (0 \\le i < M)$ 行：$X[i]\\ Y[i]\\ A[i]\\ B[i]\\ C[i]$\n+   第 $3 + M + i\\ (0 \\le i < W)$ 行：$L[i]\\ R[i]$\n\n## Output\n\n评测程序示例按照如下格式打印你的答案：\n\n+   第 $1$ 行：函数 `solve` 的返回值\n\n[samples]\n\n## Note\n\n### 样例解释\n\n对于样例一，考虑如下调用：\n\n```cpp\nsolve(3, 3, 1, {20, 30, 40}, {0, 1, 0}, {1, 2, 2},\n        {1, 20, 18}, {15, 30, 40}, {10, 5, 40}, {16}, {19});\n```\n\n一种可行的方案是依次乘坐第 $0, 1$ 次列车，花费为 $45$，具体流程如下：\n\n| 时刻 | 你的行动 | 花费 |\n| :---: | :---: | :---: |\n| $1$ | 乘坐第 $0$ 次列车从 $0$ 号行星出发 | $10$ |\n| $15$ | 到达 $1$ 号行星 |  |\n| $16$ | 在 $1$ 号行星吃第 $0$ 顿饭 | $30$ |\n| $20$ | 乘坐第 $1$ 次列车从 $1$ 号行星出发 | $5$ |\n| $30$ | 到达 $2$ 号行星 |  |\n\n一种更优的方案是乘坐第 $2$ 次列车，花费为 $40$，具体流程如下：\n\n| 时刻 | 你的行动 | 花费 |\n| :---: | :---: | :---: |\n| $18$ | 乘坐第 $2$ 次列车从 $0$ 号行星出发 | $40$ |\n| $19$ | 在第 $2$ 次列车上吃第 $0$ 顿饭 |  |\n| $40$ | 到达 $2$ 号行星 |  |\n\n在这种方案中，在时刻 $18$ 在第 $2$ 次列车上吃第 $0$ 顿饭也是合法的。\n\n因此函数应该返回 $40$。\n\n对于样例二，考虑如下调用：\n\n```cpp\nsolve(3, 5, 6, {30, 38, 33}, {0, 1, 0, 0, 1}, {2, 0, 1, 2, 2},\n        {12, 48, 26, 6, 49}, {16, 50, 28, 7, 54}, {38, 6, 23, 94, 50},\n        {32, 14, 42, 37, 2, 4}, {36, 14, 45, 40, 5, 5});\n```\n\n最优解是：乘坐第 $0$ 次列车，车费为 $38$。在第 $0$ 次列车上免费吃第 $1$ 顿饭。第 $0, 2, 3$ 顿饭在行星 $2$ 上吃 ，花费 $33 \\times 3 = 99$。 第 $4, 5$ 顿饭在行星 $0$ 上吃，花费 $30 \\times 2 = 60$。总花费为 $38 + 99 + 60 = 197$。\n\n因此函数应该返回 $197$。\n\n### 数据范围\n\n+   $2 \\le N \\le 10^5$\n+   $0 \\le M, W \\le 10^5$\n+   $0 \\le X[i], Y [i] < N, X[i] \\neq Y[i]$\n+   $1 \\le A[i] < B[i] \\le 10^9$\n+   $1 \\le T[i], C[i] \\le 10^9$\n+   $1 \\le L[i] \\le R[i] \\le 10^9$\n\n详细子任务附加限制及分值如下表所示。\n\n| 子任务编号 | 附加限制 | 分值 |\n| :---: | :---: | :---: |\n| $1$ | $N, M, A[i], B[i], L[i], R[i] \\le 10^3, W \\le 10$ | $5$ |\n| $2$ | $W = 0$ | $5$\n| $3$ | 每顿饭的用餐时间两两不交。形式化地，对于任何时刻 $z$ 满足 $1 \\le z \\le 10^9$，至多存在一个 $i\\ (0 \\le i < W)$ 使得 $L[i] \\le z \\le R[i]$。 | $30$ |\n| $4$ | 没有额外的约束条件 | $60$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10538","tags":["动态规划 DP","2024","APIO","交互题","动态规划优化"],"sample_group":[["3 3 1 \n20 30 40\n0 1 1 15 10\n1 2 20 30 5\n0 2 18 40 40\n16 19","40"],["3 5 6\n30 38 33\n0 2 12 16 38\n1 0 48 50 6\n0 1 26 28 23\n0 2 6 7 94\n1 2 49 54 50\n32 36\n14 14\n42 45\n37 40\n2 5\n4 5","197"]],"created_at":"2026-03-03 11:09:25"}}