#P14503. [2026年省队模拟联测]连

    ID: 13720 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600动态规划区间DP记忆化搜索树形DP图论最小生成树贪心

[2026年省队模拟联测]连

【题目描述】

有一个 n×mn \times m 的网格图,从上到下第 ii 行从左到右第 jj 列的格子为 (i,j)(i, j)。

第 ii 行前 aia_i 个格子为黑色,即 (i,1),(i,2),…,(i,ai)(i, 1), (i, 2), \ldots, (i, a_i),其余为白色。第 ii 行相邻两列黑色格子之间有一条边权为 viv_i 的无向边。

你需要进行 n−1n - 1 次操作,使任意两个黑色格子互相可达,操作为选择三个整数 x,y,zx, y, z,在 (x,z)(x, z) 和 (y,z)(y, z) 间添加一条边权为 ww 的边(ww 为常数),存在如下限制:

  • 1≤x<y≤n,1≤z≤m;1 \leq x < y \leq n, 1 \leq z \leq m;
  • (x,z)(x, z) 和 (y,z)(y, z) 均为黑色格子;
  • 对于 x<i<y,(i,z)x < i < y, (i, z) 为白色格子。

你需要最小化共 S=∑aiS = \sum a_i 个黑色格子之间的两两距离之和。

【输入格式】

输入的第一行包含一个非负整数 cc,表示测试点编号。c=0c = 0 表示该测试点为样例。

第二行包含三个正整数 n,m,wn, m, w,表示网格大小和常数 ww。

接下来 nn 行,第 ii 行包含两个正整数 ai,via_i, v_i,分别表示第 ii 行黑色格子数量和内部边权。

【输出格式】

输出仅一行一个正整数,表示最小距离和。

0
1 5 1
5 1
20

【数据规模与约定】

对于所有测试数据,保证:1≤n≤601 \leq n \leq 60,1≤vi,w≤1061 \leq v_i, w \leq 10^6,1≤ai≤m≤30001 \leq a_i \leq m \leq 3000,1≤S≤30001 \leq S \leq 3000。

测试点编号 n≤n \leq S≤S \leq 特殊性质
1 ~ 3 1010 无
4 ~ 7 2020 100100
8 ~ 12 3030 10001000
13 ~ 15 6060 30003000 A
16 ~ 20 无

特殊性质 A:对于 1≤i<n1 \leq i < n,保证 ai≤ai+1a_i \leq a_{i+1}。