P3406 Undersea High-Speed Railway

The railway passes through $N$ cities, each of which has a station. However, because the cities could not coordinate, each time you travel between two adjacent cities (in either direction), you must buy a separate ticket for that segment. Segment $i$ connects city $i$ and city $i+1$ ($1 \leq i < N$). If you travel farther, you need to buy multiple tickets. A paper one-way ticket for segment $i$ costs $A_i$ Boai yuan. Although coordination fell short, the companies of each segment introduced IC cards for convenience. For segment $i$, you can pay a fee of $C_i$ Boai yuan to purchase an IC card, after which each ride on this segment only deducts $B_i$ ($B_i < A_i$) yuan. IC cards can be purchased online in advance; you do not need to buy them in the corresponding city. The card fee is non-refundable and cannot be used to buy tickets. Each card can be topped up with any amount. An IC card for segment $i$ cannot be used on other segments. Uim needs to go on a business trip to visit $M$ cities, starting from city $P_1$ and visiting cities in the order $P_1, P_2, P_3, \cdots, P_M$. A city may be visited multiple times; consecutive cities in the sequence are not necessarily adjacent on the line, and they are guaranteed to be different. Now he wants to know, after the trip ends, what is the minimum amount of money he will spend in total, including the cost of paper tickets, buying IC cards, and the rides paid with IC cards.

- The first line contains two integers, $N, M$. - The next line contains $M$ integers, representing $P_i$. - The next $N - 1$ lines describe the segments: for segment $i$, three integers $A_i, B_i, C_i$.

Output a single integer, the minimum total cost.

- Buy paper tickets for $2$ to $3$ and $8$ to $9$, and buy IC cards for the others. Constraints: - For $30\%$ of the testdata, $M = 2$. - For another $30\%$ of the testdata, $N \leq 1000$, $M \leq 1000$. - For $100\%$ of the testdata, $M, N \leq 10^5$, $A_i, B_i, C_i \leq 10^5$. Translated by ChatGPT 5