32008번 - Train 서브태스크다국어언어 제한함수 구현

문제

In the year 2992, most jobs have been taken by robots. Many people hence have abundant free time, and so is your family, who just decided to go for interstellar travel!

There are $N$ reachable planets indexed from 0ドル$ to $N - 1$ and $M$ interstellar train routes. The train route $i$ (0ドル ≤ i < M$) starts from Planet $X[i]$ at time $A[i],ドル arrives in Planet $Y[i]$ at time $B[i],ドル and costs $C[i]$. Trains are the only transportation between planets, so you can only get off a train on its destination planet, and must take the next train on the same planet (transfers take no time). Formally, a sequence of trains $q[0], q[1], \dots, q[P]$ is valid to be taken if and only if for any 1ドル ≤ k ≤ P,ドル $Y [q[k - 1]] = X[q[k]]$ and $B[q[k - 1]] ≤ A[q[k]]$.

As interstellar travel is time-consuming, you realize that in addition to the train fare, the cost of meals is significant. Thankfully, interstellar trains provide unlimited food for free. That is, if you decide to take train route $i,ドル then at any time between $A[i]$ and $B[i]$ (inclusive) you can take any number of meals with no cost. But while your family is waiting for the next train on any Planet $i,ドル you have to pay for each meal at the cost $T[i]$.

Your family need to have $W$ meals, and the $i$-th (0ドル ≤ i < W$) meal can be taken instantenously at any time between $L[i]$ and $R[i]$ (inclusive).

Now at time 0ドル,ドル your family are on Planet 0ドル$. You need to figure out the minimum cost to reach Planet $N - 1$. If you cannot reach there, your answer should be $-1$.

구현

You need to implement the following function:

long long solve(int N, int M, int W, std::vector<int> T,
 std::vector<int> X, std::vector<int> Y,
 std::vector<int> A, std::vector<int> B, std::vector<int> C,
 std::vector<int> L, std::vector<int> R);

• $N$: The number of planets.
• $M$: The number of interstellar train routes.
• $W$: The number of meals.
• $T$: An array with a length of $N$. $T[i]$ represents the cost of each meal on Planet $i$.
• $X,Y ,A,B,C$: five arrays with a length of $M$. The tuple $(X[i],Y[i],A[i],B[i],C[i])$ describes the $i$-th train route.
• $L, R$: Two arrays with a length of $W$. The pair $(L[i],R[i])$ describes the time interval to have the $i$-th meal.
• This function should return the minimum cost to reach Planet $N - 1$ from Planet 0ドル$ if you can reach Planet $N - 1,ドル and $-1$ if you cannot do so.
• For each test case, this function will be called exactly once.

예제 1

Consider the following call:

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 way to reach planet $N - 1$ is by taking Train 0ドル$ and then Train 1ドル,ドル which costs 45ドル$ (the detailed calculation is shown below).

A better way to reach planet $N - 1$ is by taking Train 2ドル$ only, which costs 40ドル$ (the detailed calculation is shown below).

In this way of reaching planet $N - 1,ドル it's also valid to take meal 0ドル$ at time 18ドル$.

Therefore, the function should return 40ドル$.

예제 2

Consider the following call:

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 path is to take Train 0ドル$ with a cost of 38ドル$. Meal 1ドル$ can be taken for free on Train 0ドル$. Meals 0ドル,ドル 2ドル,ドル and 3ドル$ must be taken on Planet 2ドル$ for 33ドル \times 3 = 99$. Meals 4ドル$ and 5ドル$ must be taken on Planet 0ドル$ for 30ドル \times 2 = 60$. The total cost is 38ドル + 99 + 60 = 197$.

Therefore, the function should return 197ドル$.

입력

출력

제한

• 2ドル ≤ N ≤ 10^5$.
• 0ドル ≤ M,W ≤ 10^5$.
• 0ドル ≤ X[i],Y [i] < N,ドル $X[i] \ne Y[i]$.
• 1ドル ≤ A[i] < B[i] ≤ 10^9$.
• 1ドル ≤ T[i],C[i] ≤ 10^9$.
• 1ドル ≤ L[i] ≤ R[i] ≤ 10^9$.

서브태스크

힌트

샘플 그레이더

The sample grader reads the input in the following format:

• Line 1ドル$: $N$ $M$ $W$
• Line 2ドル$: $T[0]$ $T[1]$ $T[2]$ $\cdots$ $T[N - 1]$
• Line 3ドル + i$ (0ドル ≤ i < M$): $X[i]$ $Y[i]$ $A[i]$ $B[i]$ $C[i]$
• Line 3ドル + M + i$ (0ドル ≤ i < W$): $L[i]$ $R[i]$

The sample grader prints your answers in the following format:

• Line 1ドル$: the return value of solve

첨부

• 0-01.in 0-02.in compile_cpp.sh run_cpp.sh stub.cpp train.cpp train.h
• sample-1.in sample-1.out sample-2.in sample-2.out