← 返回题目列表

Codeforces · 1540/A

A. 很棒的图表

中文机器翻译题面 查看原题

农夫约翰有一个农场,由 $$$n$$$ 牧场组成,并通过单向道路连接。每条路都有一个权重,代表从路的起点到终点所需的时间。道路可能具有负权重,奶牛走得如此之快以至于它们回到了过去!然而,农夫约翰保证奶牛不可能陷入时间循环,它们可以通过穿越一系列道路来无限地回到过去。此外,每对牧场在每个方向上最多由一条道路连接。

不幸的是,农夫约翰丢失了农场的地图。他只记得一个数组 $$$d$$$,其中 $$$d_i$$$ 是奶牛使用一系列道路从 $$$1$$$ 牧场到达第 $$$i$$$ 牧场所需的最短时间。他的农场的成本是每条道路的权重之和,农夫约翰需要知道与他的记忆一致的农场的最小成本。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 案例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 牧场的数量。

每个测试用例的第二行包含 $$$n$$$ 空格分隔的整数 $$$d_1, d_2, \ldots, d_n$$$ ($$$0 \leq d_i \leq 10^9$$$) — 数组 $$$d$$$。保证 $$$d_1 = 0$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出与 Farmer John 的记忆一致的农场的最小可能成本。

示例

输入 #1

3
3
0 2 3
2
0 1000000000
1
0

输出 #1

-3
0
0

注意

在第一个测试用例中,可以添加道路

- 从牧场$$$1$$$到牧场$$$2$$$,时间为$$$2$$$,
- 从牧场$$$2$$$到牧场$$$3$$$,时间为$$$1$$$,
- 从牧场$$$3$$$到牧场$$$1$$$,时间为$$$-3$$$,
- 从牧场$$$3$$$到牧场$$$2$$$,时间为$$$-1$$$,
- 从牧场 $$$2$$$ 到牧场 $$$1$$$,时间为 $$$-2$$$。

在第二个测试用例中,您可以添加一条从牧场 $$$1$$$ 到牧场 $$$2$$$ 的道路,成本 $$$1000000000$$$ 和一条从牧场 $$$2$$$ 到牧场 $$$1$$$ 的道路,成本 $$$-1000000000$$$。总成本为 $$$1000000000 + -1000000000 = 0$$$。

在第三个测试用例中,您无法添加任何道路。总成本为$$$0$$$。