#2724. 「JOI 2015 Final」铁路旅行

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: fbhou

题目描述

译自 JOI 2015 Final T1「鉄道旅行

JOI 国有 N 座城市,依次编号为 1,2,\cdots ,N ;还有 N-1 条可双向通行的铁路,依次编号为 1,2,\cdots ,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 卡更容易结算费用,用 IC 卡乘车总是比用纸质车票乘车便宜。也就是说,对于 i=1,2,\cdots ,N-1 ,总有 A_{i} > B_{i} 成立。由于各条铁路的 IC 卡规格各不相同,对于任意的 i ,能在铁路 i 使用的 IC 卡并不能在其他铁路上使用。

你准备在 JOI 国旅行,从城市 P_{1} 出发,按照 P_{2},P_{3},\cdots ,P_{M} 的顺序进行参观。行程由 M-1 天组成。第 j(1\le j\le M-1) 天的计划是从城市 P_{j} 坐火车移动到 P_{j+1} 。可能会通过一些铁路中转。而且,你有可能多次参观同一座城市。因为 JOI 国的铁路速度很快,所以无论从哪座城市到哪座城市都能在 1 天之内到达。

现在你并没有任何一条铁路的 IC 卡。你想要买其中一些铁路的 IC 卡,从而使这次旅行所需的金额,也就是说,买 IC 卡和乘坐列车的费用总和最小。

任务

编写程序以输入 JOI 国的城市数、旅行的行程以及 JOI 国中每一条铁路的票价和 IC 卡价格,求出旅行所需费用的最小值。

输入格式

从标准输入输入数据,格式见下:

  • 第一行是两个由空格隔开的整数 N M ,含义如题面所述;
  • 第二行是由空格隔开的 M 个整数 P_{1},P_{2},\cdots ,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} 元,购买 IC 卡的价格为 C_{i} 元。

输出格式

输出到标准输出,仅一行一个整数,即以元为单位的总花费最小值。

样例

输入样例 1

4 4
1 3 2 4
120 90 100
110 50 80
250 70 130

输出样例 1

550

样例说明 1

在这种情况下,旅行总花费最小的方案如下:

  • 购买铁路 2 3 的 IC 卡。花去 80+130=210 元。
  • 第一天,使用纸质车票从城市 1 到城市 2 ,然后使用 IC 卡从城市 2 3 。花去 120+50=170 元。
  • 第二天,使用 IC 卡从城市 3 到城市 2 。花去 50 元。
  • 第三天,使用 IC 卡从城市 2 到城市 3 ,然后使用 IC 卡从城市 3 到城市 4 。花去 50+70=120 元。

如果像这样乘车的话,旅行的总花费为 210+170+50+120=550 元,是能够达到的最小值,因此输出 550

输入样例 2

8 5
7 5 3 5 4
12 5 8
16 2 1
3 1 5
17 12 17
19 7 5
12 2 19
4 1 3

输出样例 2

81

数据范围与提示

全部的输入数据满足:

  • 2\le N\le 10^5
  • 2\le M\le 10^5
  • 1\le B_{i} < A_{i}\le 10^5(1\le i \le N-1)
  • 1\le C_{i}\le 10^5(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 分]

没有额外限制。