python/TangDou/Topic/PrefixAndSuffix/P3406.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
#define int long long // 数据范围是10^5*10^5,所以注意要开ll
#define endl "\n"
int p[N];             // 要访问的城市顺序
int x[N], y[N], z[N]; // 买票,充值,买卡
int b[N];             // 差分数组
int res;              // 结果
int n, m;             // 共n个城市，要去m个城市

signed main() {
    cin >> n >> m;                                           // 共n个城市，要去m个城市
    for (int i = 0; i < m; i++) cin >> p[i];                 // 访问顺序,下标都是从0开始的
    for (int i = 1; i < n; i++) cin >> x[i] >> y[i] >> z[i]; // 每个城市的买票、充值、买卡价格，此处下标从1开始，是因为P0不需要再到P0

    for (int i = 1; i < m; i++) {   // 0号点是出发点，没有意义，不讨论，从1号开始，最大是 m-1
        int s = p[i - 1], t = p[i]; // 起点, 终点
        if (s > t) swap(s, t);      // 我KAO，原来题意是说：如果你从2~5去则一定走了2,3,4,5这四个城市，铁路按线段处理，即2,3,4号线段
        b[s] += 1, b[t] -= 1;       // s在内，t不在内，因为是按线段处理的
    }

    for (int i = 1; i <= n; i++) b[i] += b[i - 1]; // 差分数组变形为前缀和数组

    // 判断一下 n*a[i]和n*b[i]+c[i]的大小
    for (int i = 1; i < n; i++)
        res += min(b[i] * x[i], b[i] * y[i] + z[i]);
    // b[i]:走几次，x[i]*b[i]:买票需要花费多少钱；b[i] * y[i] + z[i]:办卡+冲值共需要花费多少钱
    // 两个打擂台，谁少就用谁，每一块线段都花费最少，整体必须花费最少，贪心
    cout << res << endl; // 输出
}