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
输入 #1
4 4
1 3 2 4
120 90 100
110 50 80
250 70 130
输出 #1
550
输入输出样例 #2
输入 #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
说明/提示
样例解释 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 完成
思路概述
众所周知，差分数组的前缀和就是原数组。
题目中 \(l\) 到 \(r\) 的一次旅行，就相当于把 \(l\) 与 \(r\) 之间的每一条边都遍历一遍。如果边从 \(1\) 开始编号，那么就相当于编号 \(l+1\) ~ \(r\) 的边都遍历一遍。那就是区间操作，可以用差分。最后跑一趟前缀和，得到每条边遍历了多少次。
那么接下来就很简单了：便利每条边，如果走 \(IC\) 更便宜，那么我们就加上 \(IC\) 票钱与 \(IC\) 路程费；如果纸票便宜，那就直接付路程费。
代码示例
#include <bits/stdc++.h>
#define N 200010
#define M 200010
using namespace std;
typedef long long ll;
int n,m;
ll ans;
int p[M],a[N],b[N],c[N];
int cnt[N];
bool ic[N];
int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) scanf("%d",&p[i]);for(int i=1;i<n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);for(int i=1;i<m;i++) {cnt[min(p[i],p[i+1])]++;cnt[max(p[i],p[i+1])]--;}for(int i=1;i<n;i++) cnt[i]+=cnt[i-1];for(int i=1;i<n;i++) {if(!ic[i]) {if((ll)a[i]*cnt[i]<(ll)b[i]*cnt[i]+c[i])ans+=(ll)a[i]*cnt[i];else {ic[i]=true;ans+=(ll)b[i]*cnt[i]+c[i];}}else ans+=(ll)b[i]*cnt[i];}printf("%lld\n",ans);return 0;
}