JOI 先生管理着 IOI 高原上一家著名的滑雪度假村,他决定为滑雪度假村开业 15 周年庆祝活动而在相邻的 KOI 高原上建造一家新的滑雪度假村。
KOI 高原有
JOI 先生的目标是在高原上的一个点上建造 KOI 酒店,然后建造一些滑道连接高原上的每个点,以便人们可以从任何一个点滑雪到酒店。具体来说,JOI 先生将按照以下步骤建造滑雪度假村:
进行以下筑堤工作任意次数(可能为零):选择一个点
,将点 的海拔高度增加 1 米。此工作的成本为每次操作 。从
个点中选择一个点,并在那里建造 KOI 酒店。进行以下扩展工作任意次数(可能为零):选择一个点
,在点 建造一个连接设施。此工作的成本为每次操作 。对于除了 KOI 酒店所在点之外的剩余
个点,执行以下构建:设 为该点的编号。选择另一个海拔严格较低的点 ,并使用点 的一个未使用的连接设施,从点 向点 构建单向滑道。注意,如果没有海拔严格较低且有未使用连接设施的点 ,则无法实现目标。
滑雪度假村的建造成本是进行堤岸工作和扩展工作的成本之和。
编写一个程序,给定 KOI 高原上每个点的信息和每次筑堤工作的成本
输入格式
从标准输入中读取以下数据:
- ...
输出格式
输出一行,构建滑雪度假村的最小成本。
样例输入 1
5 2 0 6 1 1 0 5 2 1 1 2
样例输出 1
8
样例解释 1
例如,可以按以下方式建造滑雪度假村:
- 在点
进行两次筑堤工作,在点 进行一次。这些筑堤工作的总成本为 。每个点的海拔高度变为 米。 - 在点
建造 KOI 酒店。 - 在点
进行两次扩展工作。这些扩展工作的总成本为 。结果,从点 开始,每个点的连接设施数量变为 。 - 构建
条滑道:一条从点 到点 ,一条从点 到点 ,一条从点 到点 ,一条从点 到点 。
因此,构建滑雪度假村的成本为
此样例输入满足子任务
样例输入 2
5 100000 0 6 1 1 0 5 2 1 1 2
样例输出 2
100010
样例解释 2
这个样例输入与示例输入 1 的唯一区别在于
这个样例输入满足子任务
样例输入 3
8 8 0 36 1 47 2 95 0 59 1 54 0 95 1 87 2 92
样例输出 3
108
样例解释 3
此示例输入满足子任务
约束条件
( ) ( )- 给定的值均为整数。
子任务
- (5 分)
, , ( ) - (12 分)
, , ( ) - (9 分)
, ( ) - (33 分)
, ( ) - (27 分)
( ) - (14 分) 无额外约束。