题目详情题解（0）讨论（0）提交记录（0）

AT_joi2015ho_a.鉄道旅行 (Railroad Trip)

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

JOI 国有 NN 个城市，编号分别为 1,2,…,N1, 2, \ldots, N。此外，有 N−1N-1 条铁路，编号分别为 1,2,…,N−11, 2, \ldots, N-1。铁路 ii（1≤i≤N−11 \leq i \leq N-1）连接城市 ii 和城市 i+1i+1，且为双向铁路。

在 JOI 国乘坐铁路有两种方式：使用纸质车票，或使用 IC 卡。

  • 乘坐铁路 ii 时，使用纸质车票的票价为 AiA_i 日元。
  • 乘坐铁路 ii 时，使用 IC 卡的票价为 BiB_i 日元。但要用 IC 卡乘坐铁路 ii，需要事先购买该铁路专用的 IC 卡，购买费用为 CiC_i 日元。已购买的 IC 卡可以无限次使用。
  • 由于 IC 卡结算更方便，IC 卡乘坐铁路的票价总是低于纸质车票，即对于所有 i=1,2,…,N−1i=1,2,\ldots,N-1，都有 Ai>BiA_i > B_i。
  • 每条铁路的 IC 卡互不通用，即铁路 ii 的 IC 卡不能用于其他铁路。

你打算在 JOI 国旅行。从城市 P1P_1 出发，按顺序依次访问 P2,P3,…,PMP_2, P_3, \ldots, P_M。旅行共持续 M−1M-1 天。第 jj 天（1≤j≤M−11 \leq j \leq M-1），你将从城市 PjP_j 乘坐铁路前往城市 Pj+1P_{j+1}。途中可以换乘多条铁路，也可能多次访问同一城市。JOI 国的铁路很快，任意两城市之间都能在一天内到达。

你现在还没有任何铁路的 IC 卡。你可以事先购买若干铁路的 IC 卡。请你最小化本次旅行的总花费（IC 卡购买费用与乘坐铁路的票价之和）。

输入格式

从标准输入读取以下数据。

  • 第 11 行包含两个整数 N,MN, M，分别表示 JOI 国有 NN 个城市，旅行共 M−1M-1 天。
  • 第 22 行包含 MM 个整数 P1,P2,…,PMP_1, P_2, \ldots, P_M，表示第 jj 天（1≤j≤M−11 \leq j \leq M-1）从城市 PjP_j 前往城市 Pj+1P_{j+1}。
  • 接下来 N−1N-1 行，第 ii 行（1≤i≤N−11 \leq i \leq N-1）包含三个整数 Ai,Bi,CiA_i, B_i, C_i，分别表示铁路 ii 的纸质车票票价 AiA_i，IC 卡票价 BiB_i，以及该铁路 IC 卡的购买费用 CiC_i。

输出格式

输出一个整数，表示本次旅行的最小总花费（日元）。

输入输出样例

  • 输入#1

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

    输出#1

    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

说明/提示

任务

给定 JOI 国的城市数量、旅行路线，以及每条铁路的票价和 IC 卡价格，编写程序求出本次旅行的最小总花费。

限制

所有输入数据满足以下条件。

  • 2≤N≤100 0002 \leq N \leq 100\,000。
  • 2≤M≤100 0002 \leq M \leq 100\,000。
  • 1≤Bi<Ai≤100 0001 \leq B_i < A_i \leq 100\,000（1≤i≤N−11 \leq i \leq N-1）。
  • 1≤Ci≤100 0001 \leq C_i \leq 100\,000（1≤i≤N−11 \leq i \leq N-1）。
  • 1≤Pj≤N1 \leq P_j \leq N（1≤j≤M1 \leq j \leq M）。
  • Pj≠Pj+1P_j \neq P_{j+1}（1≤j≤M−11 \leq j \leq M-1）。

子任务

子任务 1 [20 分]

满足以下条件。

  • 2≤N≤1 0002 \leq N \leq 1\,000。
  • M=2M = 2。
  • 1≤Bi<Ai≤1 0001 \leq B_i < A_i \leq 1\,000（1≤i≤N−11 \leq i \leq N-1）。
  • 1≤Ci≤1 0001 \leq C_i \leq 1\,000（1≤i≤N−11 \leq i \leq N-1）。

子任务 2 [30 分]

满足以下条件。

  • 2≤N≤1 0002 \leq N \leq 1\,000。
  • 2≤M≤1 0002 \leq M \leq 1\,000。
  • 1≤Bi<Ai≤1 0001 \leq B_i < A_i \leq 1\,000（1≤i≤N−11 \leq i \leq N-1）。
  • 1≤Ci≤1 0001 \leq C_i \leq 1\,000（1≤i≤N−11 \leq i \leq N-1）。

子任务 3 [50 分]

无额外限制。

样例解释 1

在本例中，最优的旅行方案如下：

  • 购买铁路 22 和铁路 33 的 IC 卡，费用为 80+130=21080 + 130 = 210 日元。
  • 第 11 天，从城市 11 到城市 22 使用纸质车票，再从城市 22 到城市 33 使用 IC 卡，费用为 120+50=170120 + 50 = 170 日元。
  • 第 22 天，从城市 33 到城市 22 使用 IC 卡，费用为 5050 日元。
  • 第 33 天，从城市 22 到城市 33 使用 IC 卡，再从城市 33 到城市 44 使用 IC 卡，费用为 50+70=12050 + 70 = 120 日元。

这样，总花费为 210+170+50+120=550210 + 170 + 50 + 120 = 550 日元。由于这是最小值，输出 550550。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页