2753: C.高速公路
题目描述
A国有 n 个城市，编号依次为 1 , 2 … n 。有 n - 1 条高速公路，其中，第 i 条高速公路连接城市 i 与 i ＋ 1 。n 个城市依次排成一条链，每条高速公路可以双向通行（费用相同）。
每条高速公路的收费各不相同，分为两种收费方式：
- 对于高速公路 i ，不购买年卡，单次通行价格为 ai 元。
- 对于高速公路 i ，购买年卡花费 ci 元，使用年卡通过该高速公路，单次通行价格 bi 元（ bi ＜ ai )。
每条高速公路的年卡是独立的，不能在其他高速公路上使用。
有一名新手货车司机，有 m 1 个运输任务, 从城市 D1 出发，接下来需要依次去往城市
D2 , D3 , · · · , Dm 。第 j个运输任务需要从城市 Dj 去往 Dj＋1 ，可能会经过多条高速公路。
货车司机没有经验，需要你来帮助他，通过购买某些高速公路的年卡，使他完成所有运输任务所花费的 费用最小。
输入
第一行两个整数 n，m。
接下来一行 m 个整数，第 i 个整数表示 Di 。
接下来 n 1 行，每行三个整数，其中第 i 行的三个整数依次表示第 i 条公路的 ai , bi , ci 。
输出
一个整数，表示货车司机需要花费的最少费用。
样例输入 复制
4 4
1 4 2 3
130 100 90
120 60 80
100 65 75样例输出 复制
590提示
样例解释 #1
货车司机依次走的城市： 1 2 3 4 3 2 3
货车司机总花费最小的方案如下：
购买第2条高速公路 的 年卡，花去 80 元。
1到2不使用年卡，费用130；
2到3使用年卡，费用60；
3到4不使用年卡，费用100；
4到3不使用年卡，费用100；
3到2使用年卡，费用60；
2到3使用年卡，费用60。
总花费为590。
提示
全部数据满足：
2 ≤ N ≤ 105
2 ≤ M ≤ 105
1 ≤ Bi ＜ Ai ≤ 105 (1≤ i ≤ N -1)
1 ≤ ci ≤ 105(1 ≤ i ≤ N - 1)
1 ≤ Dj ≤ N(1 ≤ j ≤ M)
Dj ≠ Dj＋1 （1≤ j ≤ M - 1)
对于 20% 的数据，满足以下条件：
2 ≤ N ≤ 1000
M ＝ 2
1 ≤ Bi ＜ Ai ≤ 1000(1 ≤ i ≤ N -1)
1 ≤ ci ≤ 1000(1 ≤ i ≤ N - 1)
对于另外 30% 的数据，满足以下条件：
2 ≤ N ≤ 1000
2 ≤ M ≤ 1000
1 ≤ Bi < Ai ≤ 1000(1 ≤ i ≤ N -1)
1 ≤ ci ≤ 1000(1 ≤ i ≤ N - 1)
对于另外 50% 的数据，无额外限制。