#2929. [GDKOI]城市建设

[GDKOI]城市建设

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

现在有 NN 个城市分别位于 1,2,...,N1,2, ..., N 号节点上。作为城市的管理者小明希望花最小的代价把这 NN 个城 市联通起来。联通城市的花费主要分为下面两种。

第一种:建设道路,在 aa 号城市和 bb 号城市之间建设道路将会花费 ab|a− b| 的代价;

第二种:设置管理城市,对于一个城市 XX 可以使用 CC 的代价将其升级为管理城市; 在保证每条道路至少联结一个管理城市,以及非管理城市只能连接一条边的前提下,小明想知道他最少 能用多少的代价使所有城市联通

输入格式

第一行一个正整数 NN,表示城市数量;

第二行一个整数 CC,表示设置管理城市的代价。

输出格式

一行,一个整数,表示小明使城市联通的最小代价。

输入样例1

6
3

输出样例1

12

输入样例2

1000
1000

输出样例2

32561

输入样例3

100000
10000

输出样例3

10099799

样例解释

2,52,5 分别为管理城市,并联结 (1,2),(2,3),(2,5),(4,5),(5,6)(1,2),(2,3),(2,5),(4,5),(5,6) 共五条边时取得最小代价; 也可以以 3344 作为管理城市,并联结其余所有点,此时也取得最小代价。

数据范围

对于 20%20\% 的数据,1N201 ≤ N ≤ 20

对于 40%40\% 的数据,1N1031 ≤ N ≤ 10^3;

对于另外 20%20\% 的数据,1N105,0C1041 ≤ N ≤ 10^5,0 ≤ C ≤ 10^4;

对于 100%100\% 的数据,1N109,0C1091 ≤ N ≤ 10^9,0 ≤ C ≤ 10^9

少年宫中心团队day1

未参加
状态
已结束
规则
IOI
题目
7
开始于
2024-1-17 9:00
结束于
2024-1-17 12:00
持续时间
3 小时
主持人
参赛人数
19