P15816 [JOI 2015 Final] 铁路旅行 / Railroad Trip
题目描述
JOI 国有 $N$ 个城市，编号分别为 $1, 2, \dots, N$。此外，有 $N-1$ 条铁路，编号分别为 $1, 2, \dots, N-1$。铁路 $i$ ($1 \le i \le N-1$) 双向连接城市 $i$ 和城市 $i+1$。
在 JOI 国乘坐铁路有两种方式：使用纸质车票和使用 IC 卡。
* 乘坐铁路 $i$ 时，若使用纸质车票，票价为 $A_i$ 日元。
* 乘坐铁路 $i$ 时，若使用 IC 卡，票价为 $B_i$ 日元。但是，要使用 IC 卡乘坐铁路 $i$，必须事先购买能在铁路 $i$ 上使用的 IC 卡。购买一张能在铁路 $i$ 上使用的 IC 卡需要花费 $C_i$ 日元。一旦购买，该 IC 卡可以无限次使用。
由于 IC 卡处理金额更为简便，使用 IC 卡乘车的票价低于使用纸质车票的票价。也就是说，对于所有 $i=1,2,\dots,N-1$，均有 $A_i > B_i$ 成立。每条铁路的 IC 卡规格完全不同，因此对于任何 $i$，能在铁路 $i$ 上使用的 IC 卡都不能用于其他铁路。
你计划周游 JOI 国。你将从城市 $P_1$ 出发，并按照 $P_2, P_3, \dots, P_M$ 的顺序访问城市。旅行由 $M-1$ 天的行程组成。在第 $j$ 天 ($1 \le j \le M-1$)，你将从城市 $P_j$ 乘坐铁路前往城市 $P_{j+1}$。此时，可能需要换乘多条铁路。此外，你可能会多次访问同一个城市。JOI 国的铁路速度很快，因此任何两个城市之间都可以在一天内到达。
目前，你没有持有任何铁路的 IC 卡。你希望提前购买一些铁路的 IC 卡，使得这次旅行的总花费（即 IC 卡购买费用与乘坐铁路的票价之和）尽可能少。
### 任务
给定 JOI 国的城市数量、旅行行程以及每条铁路的票价和 IC 卡价格。请编写一个程序，计算旅行总花费的最小值。
输入格式
从标准输入读取以下数据。
* 第一行包含两个以空格分隔的整数 $N, M$。它们分别表示 JOI 国有 $N$ 个城市，旅行包含 $M-1$ 天的行程。
* 第二行包含 $M$ 个以空格分隔的整数 $P_1, P_2, \dots, P_M$。它们表示在第 $j$ 天 ($1 \le j \le M-1$)，将从城市 $P_j$ 前往城市 $P_{j+1}$。
* 接下来的 $N-1$ 行中，第 $i$ 行 ($1 \le i \le N-1$) 包含三个以空格分隔的整数 $A_i, B_i, C_i$。它们分别表示乘坐铁路 $i$ 时，使用纸质车票的票价为 $A_i$ 日元，使用 IC 卡的票价为 $B_i$ 日元，购买能在铁路 $i$ 上使用的 IC 卡的价格为 $C_i$ 日元。
输出格式
向标准输出输出一行，包含一个整数，表示旅行总花费的最小值（单位：日元）。
说明/提示
### 样例解释 1
在这种情况下，使旅行总花费最小的方案如下：
* 购买铁路 2 和铁路 3 的 IC 卡。这需要花费 $80 + 130 = 210$ 日元。
* 第一天，从城市 1 使用纸质车票前往城市 2，然后从城市 2 使用 IC 卡前往城市 3。这需要花费 $120 + 50 = 170$ 日元。
* 第二天，从城市 3 使用 IC 卡前往城市 2。这需要花费 $50$ 日元。
* 第三天，从城市 2 使用 IC 卡前往城市 3，然后从城市 3 使用 IC 卡前往城市 4。这需要花费 $50 + 70 = 120$ 日元。
按照这种方式移动，旅行总花费为 $210 + 170 + 50 + 120 = 550$ 日元。这是最小值，因此输出 $550$。
### 数据范围
所有输入数据满足以下条件：
* $2 \le N \le 100\,000$。
* $2 \le M \le 100\,000$。
* $1 \le B_i < A_i \le 100\,000$ ($1 \le i \le N-1$)。
* $1 \le C_i \le 100\,000$ ($1 \le i \le N-1$)。
* $1 \le P_j \le N$ ($1 \le j \le M$)。
* $P_j \ne P_{j+1}$ ($1 \le j \le M-1$)。
### 子任务
#### 子任务 1 [20 分]
满足以下条件：
* $2 \le N \le 1000$。
* $M = 2$。
* $1 \le B_i < A_i \le 1000$ ($1 \le i \le N-1$)。
* $1 \le C_i \le 1000$ ($1 \le i \le N-1$)。
#### 子任务 2 [30 分]
满足以下条件：
* $2 \le N \le 1000$。
* $2 \le M \le 1000$。
* $1 \le B_i < A_i \le 1000$ ($1 \le i \le N-1$)。
* $1 \le C_i \le 1000$ ($1 \le i \le N-1$)。
#### 子任务 3 [50 分]
没有额外限制。
翻译由 DeepSeek V3.2 完成