游戏关卡(Game Levels)

题目描述

小 Z 正在玩有一个游戏。游戏由编号为 $1,2,\cdots,n$ 的 $n$ 个关卡组成。最初，只能玩第 $1$ 关。

对于每个可以玩的关卡 $i(1\le i \le n - 1)$，你可以在关卡 $i$ 执行以下两个操作之一：

• 花费 $a_i$ 秒来通关关卡 $i$。这使得你能够玩下一个关卡 $i+1$。
• 花费 $b_i$ 秒来通关关卡 $i$。这使得你能够玩关卡 $x_i$。

忽略所有除了完成关卡所需时间之外的其他时间，最少需要多少秒才能玩到第 $n$ 关？

输入格式

输入的第一行包含一个整数 $n$，表示关卡数量。

接下来有 $n-1$ 行，每行输入三个整数 $a_i,b_i,x_i$，含义如题。

输出格式

输出一行一个整数表示答案。

样例输入 #1

5
100 200 3
50 10 1
100 200 5
150 1 2

样例输出 #1

350

样例输入 #2

10
1000 10 9
1000 10 10
1000 10 2
1000 10 3
1000 10 4
1000 10 5
1000 10 6
1000 10 7
1000 10 8

样例输出 #2

90

样例输入 #3

6
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1
1000000000 1000000000 1

样例输出 #3

5000000000

数据范围

样例 1 解释：

• 花费 $100$ 秒通关 $1$ 号关卡，然后来到 $2$ 号关卡。
• 花费 $50$ 秒通过 $2$ 号关卡，来到 $3$ 号关卡。
• 花费 $200$ 秒通过 $3$ 号关卡，来到 $5$ 号关卡。

$2\le n \le 2 \times 10^5,1\le a_i,b_i \le 10^9,1\le x_i \le n$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1400。

测试点分布

出处：原题链接