#P18380. Traveling in Cells 3
Traveling in Cells 3
Traveling in Cells 3
题目描述
小青鱼王国可以看成一条由 个格子组成的直线,格子的编号依次为 。
小青鱼要为下一届 Universal Cup 总决赛选择举办地点。目前有 支获得参赛资格的队伍,第 支队伍位于编号为 的格子。所有队伍都要前往同一个举办格子。
王国中有两种交通方式,可以任意组合使用:
- 铁路:从格子 移动到相邻格子 或 ,每次花费 美元。
- 航班:从格子 移动到格子 或 ,每次花费 美元。
举办地点可以选择王国中的任意一个格子,不要求已有队伍位于该格子。小青鱼只关心总花费,不关心旅行时间。
请最优地选择举办地点及每支队伍的旅行方式,使所有队伍抵达举办地点的总花费最小,并输出这个最小值。
输入格式
第一行一个整数 (),表示测试用例数。
每个测试用例包含两行:
- 第一行三个整数 ,其中 ,。
- 第二行 个整数 ,其中 。队伍的位置可以重复。
保证一个输入文件中所有测试用例的 之和不超过 。
输出格式
每个测试用例输出一行,一个整数,表示最小总花费。
样例输入 1
3
3 5 1
1 11 22
4 5 3
1 3 5 8
7 6 3
2 9 15 24 33 40 53
样例输出 1
5
7
55
样例说明
对第一个测试用例,可在编号 的格子举办比赛:
- 位于 的队伍乘坐两次航班:,花费 。
- 位于 的队伍无需移动,花费 。
- 位于 的队伍先乘坐两次航班,再乘坐一次铁路:,花费 。
总花费为 。下图为旅行路线示意。
