← 返回题目列表

AtCoder · abc340_d

G. 超级高桥兄弟。

中文机器翻译题面 查看原题

分数: 425 点

问题陈述

高桥正在玩游戏。

游戏包括 N 阶段编号 1,2,\ldots,N。最初只是阶段性的 可以播放 1 。

对于每个阶段 i ( 1\leq i \leq N-1 )可以播放,您可以在舞台上执行以下两个操作之一 i:

  • 花费 A_i 秒数通关 i。这可以让你玩舞台 i+1.
  • 花费 B_i 秒数通关 i。这可以让你玩舞台 X_i.

不考虑通关时间以外的时间,最少需要多少秒才能玩完关卡 N?

约束

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq A_i, B_i \leq 10^9
  • 1 \leq X_i \leq N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 B_1 X_1
A_2 B_2 X_2
\vdots
A_{N-1} B_{N-1} X_{N-1}

输出

打印答案。


示例输入 1

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

示例输出 1

350

通过执行以下操作,您将被允许上台 5 in 350 秒。

  • 花费 100 秒数通关 1,允许您玩舞台 2.
  • 花费 50 秒数通关 2,允许您玩舞台 3.
  • 花费 200 秒数通关 3,允许您玩舞台 5.

示例输入 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