CF1540A Great Graphs

农夫 John 有一个农场，由 $n$ 个牧场组成，这些牧场通过单向道路连接。每条道路都有一个权值，表示从起点到终点所需的时间。道路的权值可以为负数，这意味着奶牛们跑得太快，以至于回到了过去！不过，农夫 John 保证奶牛们不可能陷入时间循环，也就是说，不存在一条道路序列使得奶牛们可以无限次地回到过去。此外，每对牧场之间每个方向最多只有一条道路。 不幸的是，农夫 John 把农场的地图弄丢了。他只记得一个数组 $d$，其中 $d_i$ 表示奶牛们从牧场 $1$ 出发，通过一系列道路到达第 $i$ 个牧场所需的最短时间。农场的代价定义为所有道路权值之和。农夫 John 需要知道，与他的记忆一致的农场的最小可能代价是多少。

第一行包含一个整数 $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$。

对于每个测试用例，输出一个与农夫 John 的记忆一致的农场的最小可能代价。

在第一个测试用例中，你可以添加如下道路： - 从牧场 $1$ 到牧场 $2$，时间为 $2$， - 从牧场 $2$ 到牧场 $3$，时间为 $1$， - 从牧场 $3$ 到牧场 $1$，时间为 $-3$， - 从牧场 $3$ 到牧场 $2$，时间为 $-1$， - 从牧场 $2$ 到牧场 $1$，时间为 $-2$。 总代价为 $2 + 1 + (-3) + (-1) + (-2) = -3$。 在第二个测试用例中，你可以添加一条从牧场 $1$ 到牧场 $2$ 的道路，代价为 $1000000000$，以及一条从牧场 $2$ 到牧场 $1$ 的道路，代价为 $-1000000000$。总代价为 $1000000000 + (-1000000000) = 0$。 在第三个测试用例中，你不能添加任何道路。总代价为 $0$。 由 ChatGPT 4.1 翻译