思路

设铁路 $i$ 被经过的次数为 $cnt_i$，则总花费为：

$A_i > B_i$ 较大时，购买 IC 卡更划算；否则直接买纸质票更划算。

由于城市是线性排列的，从城市 $u$ 到城市 $v$（假设 $u<v$）会经过铁路 $u$，$u+1$，$\dots$，$v−1$。因此只需统计每条铁路被所有行程经过的总次数。

统计我用了差分数组，对于每个行程 $(P_j,P_j+1)$，令 $l = \min(P_j,P_j+1)$，$r = \max(P_j,P_j+1)$。则经过的铁路区间是 $\lbrack l,r \rparen$。让 $diff[l]$ 加一，$diff[r]$ 减一。最后对 $diff$ 求前缀和，得到每条铁路的经过次数 $cnt_i$。

时间复杂度 $O(N+M)$。 ::::success[AC CODE]{open}

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> P(m);
    for(int i = 0; i < m; i++)cin >> P[i];
    vector<long long> a(n - 1), b(n - 1), c(n - 1);
    for(int i = 0; i < n - 1; i++)
        cin >> a[i] >> b[i] >> c[i];
    //差分数组，下标从 1 到 N
    vector<long long> diff(n + 2, 0);
    for(int j = 0; j < m - 1; j++){
        int u = P[j], v = P[j + 1];
        int l = min(u, v);
        int r = max(u, v);
        diff[l] += 1;
        diff[r] -= 1;
    }
    //前缀和得到每条铁路的经过次数
    vector<long long> count(n - 1);
    long long cur = 0;
    for(int i = 1; i < n; i++){
        cur += diff[i];
        count[i - 1] = cur; //cnt[0] 对应铁路 1
    }
    long long total = 0;
    for(int i = 0; i < n - 1; i++)
        total += min(count[i] * a[i], c[i] + count[i] * b[i]);
    cout << total << endl;
    return 0;
}

::::