题解

题面描述

在某异界大陆，从城池 $A$ 到达城池 $B$ 需要经过若干个传送阵。 $A$ 城设有起点传送阵， $B$ 城设有终点传送阵。所有传送阵按一条直线排列，相邻传送阵之间的距离均为 $1$ 。每个传送阵具有以下两个属性：

1000ms

Difficulty: 6

所属公司 : 华为

算法与标签>最短路算法

某异界大陆，从城池 $A$ 到达城池 $B$ 需要经历若干个传送阵， $A$ 城有起点传送阵， $B$ 城为终点，传送阵呈一字排开，相邻传送阵之间距离都为 $1$ 。每个传送阵可传送距离是 $1$ 到 $L$ ，每次传送消耗的能量水晶 $i$ 个，传送阵只能向前传送，不可向后。

修士小明携带若干能量水晶从 $A$ 城出发，请问小明最少需要携带多少水晶才能到达 $B$ 城。

输入为多行:

第一行为整数 $m(0<m<=10^4)$ ，表示接下来 $m$ 行数组元素( $m$ 个传送阵)

第二行至第 $m+1$ 行为长度为2的整数数组，两个整数以空格隔开，第一个元素表示传送阵可传送的最大距离 $L(0<L<=m)$ ，第二个元素表示该传送阵每次传送消耗的能量水晶个数 $i(0<i<=10^4)$

输出为整数，表示最少需要携带的水晶个数

输入

输出

说明

从下标 $0$ 的传送阵出发，最优路径:

$0->2->B$ 城，,需要 $5$ 个水晶。

到达B城最少需要 $5$ 个水晶。

输入

输出

说明

从下标 $0$ 的传送阵出发，只能到达传送阵 $1$ ，最优路径:

$0->1->3->B$ 城，,需要 $4$ 个水晶。

到达B城最少需要 $4$ 个水晶。

输入

预期输出（选填）