运输
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
问题描述
松鼠王国有 个城市,城市与城市之间有道路相连,有 条道路,保证任意两个城市连通。每条道路都有边权。
现在,每个城市都贮存了一些松果。将 个松果从 城市运送到 城市的代价为 ,其中 为 城市到 城市的距离,定义为从 城市到 城市最短路径的边权之和。国王想要通过以一定的方式运输这些松果,使得每个城市最后的松果数尽可能平均。即是每个城市松果数的方差尽可能小。
求最小的运输代价,使得每个城市松果数的方差最小。
输入格式
第一行一个整数 ,表示测试点数目。
对于每个测试点,第一行一个整数 ,表示城市数目,接下来一行 个整数 ,表示第 个城市原始的松果数量。接下来 行,每行三个整数 ,表示有一条边连接第 和第 个城市,边权为 。
输出格式
输出有 行,每行为一个测试点的最小运输代价。
3
3
1 2 3
1 2 1
1 3 1
3
1 3 3
1 2 3
1 3 4
2
1 2
1 2 19
1
3
0
数据范围
对于 的数据, 。 对于 的数据, 。 对于 的数据, 。
虚假的比赛
- Status
- Done
- Rule
- IOI
- Problem
- 4
- Start at
- 2023-10-6 8:00
- End at
- 2023-10-7 8:00
- Duration
- 24 hour(s)
- Host
- Partic.
- 56