P10538 [APIO2024] Interstellar Train

**Do not submit using C++14 (GCC 9).** In the year 2992, robots have replaced most human work, and everyone has a lot of free time. Therefore, you and your family decide to use this time for an interstellar trip. There are $N$ planets reachable by humans, numbered from $0$ to $N - 1$, and $M$ different interstellar train routes. The $i$-th train route ($0 \le i < M$) departs from planet $X[i]$ at time $A[i]$, arrives at planet $Y[i]$ at time $B[i]$, and costs $C[i]$. Between planets, these interstellar trains are the only means of transportation. For any interstellar train you take, you can only get off at its terminal station, and the departure planet of your next train must be the same as the arrival planet of the previous train (assume transfers take no time). Formally, you can take trains $q[0], q[1], \ldots, q[P]$ in order if and only if for every $1 \le k \le P$ we have $Y[q[k - 1]] = X[q[k]]$ and $B[q[k - 1]] \le A[q[k]]$. Traveling between different planets is very time-consuming, so besides ticket costs, meal expenses cannot be ignored. Unlimited food is provided for free on trains, meaning eating on a train costs nothing: if you decide to take the $i$-th interstellar train, then at any moment between $A[i]$ and $B[i]$ (including endpoints) you may eat any number of meals for free. However, if you decide to eat on planet $i$, each meal costs $T[i]$. During the trip, you and your family need to eat a total of $W$ meals. The $i$-th meal $(0 \le i < W)$ can be eaten at any time between $L[i]$ and $R[i]$ (including endpoints), and eating takes no time. There is no required order for meals; for example, it is allowed to eat meal $1$ before meal $0$ (see sample $2$). It is now time $0$, and you and your family are on planet $0$. You need to find the minimum total cost to reach planet $N - 1$, where the cost is defined as the sum of ticket costs and meal costs. If it is impossible to reach planet $N - 1$, the minimum cost is defined as $-1$. ### Implementation Details You do not need to include the library `train.h` at the beginning of your program. You only need to implement the following function: ```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$: the number of planets. + $M$: the number of interstellar train routes. + $W$: the number of meals that must be eaten. + $T$: an array of length $N$. $T[i]$ is the cost of each meal on planet $i$. + $X, Y, A, B, C$: five arrays of length $M$. $(X[i], Y[i], A[i], B[i], C[i])$ describes the $i$-th train route. + $L, R$: two arrays of length $W$. $(L[i], R[i])$ describes the time window of the $i$-th meal. + You should return the minimum total cost to reach planet $N - 1$ from planet $0$. If planet $N - 1$ is unreachable, return $-1$. + In each test case, this function is called exactly once. #

The sample grader reads input in the following format: + Line $1$: $N\ M\ W$ + Line $2$: $T[0]\ T[1]\ T[2]\ \ldots\ T[N - 1]$ + Line $3 + i\ (0 \le i < M)$: $X[i]\ Y[i]\ A[i]\ B[i]\ C[i]$ + Line $3 + M + i\ (0 \le i < W)$: $L[i]\ R[i]$ #

The sample grader prints your answer in the following format: + Line $1$: the return value of the function `solve`. #

### Sample Explanation For sample 1, consider the following call: ```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}); ``` One feasible plan is to take trains $0, 1$ in order, with a total cost of $45$. The detailed process is as follows: | Time | Your action | Cost | | :---: | :---: | :---: | | $1$ | Take train $0$ and depart from planet $0$ | $10$ | | $15$ | Arrive at planet $1$ | | | $16$ | Eat meal $0$ on planet $1$ | $30$ | | $20$ | Take train $1$ and depart from planet $1$ | $5$ | | $30$ | Arrive at planet $2$ | | A better plan is to take train $2$, with a total cost of $40$. The detailed process is as follows: | Time | Your action | Cost | | :---: | :---: | :---: | | $18$ | Take train $2$ and depart from planet $0$ | $40$ | | $19$ | Eat meal $0$ on train $2$ | | | $40$ | Arrive at planet $2$ | | In this plan, eating meal $0$ on train $2$ at time $18$ is also valid. Therefore, the function should return $40$. For sample 2, consider the following call: ```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}); ``` The optimal solution is: take train $0$, with a ticket cost of $38$. Eat meal $1$ for free on train $0$. Eat meals $0, 2, 3$ on planet $2$, costing $33 \times 3 = 99$. Eat meals $4, 5$ on planet $0$, costing $30 \times 2 = 60$. The total cost is $38 + 99 + 60 = 197$. Therefore, the function should return $197$. ### Constraints + $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$ The detailed additional constraints and scores for subtasks are shown in the table below. | Subtask ID | Additional Constraints | Score | | :---: | :---: | :---: | | $1$ | $N, M, A[i], B[i], L[i], R[i] \le 10^3, W \le 10$ | $5$ | | $2$ | $W = 0$ | $5$ | | $3$ | The time windows of all meals are pairwise disjoint. Formally, for any time $z$ with $1 \le z \le 10^9$, there exists at most one $i\ (0 \le i < W)$ such that $L[i] \le z \le R[i]$. | $30$ | | $4$ | No additional constraints. | $60$ | Translated by ChatGPT 5