Repairman

The traveling repairman problem (TRP) is classical NP-Hard problem, which is also known as minimum latency problem (MLP) and delivery man problem. Suppose that we have a graph with n nodes, in each one there is a machine that has to be repaired, and there is only one repairman. We are given the time required by the repairman to travel among nodes. The objective is to find a tour that minimizes the total waiting time of all the machines. (ignore time of repairing)

Now for simplicity, we place all nodes on a straight line. Your task is to find out smallest sum of waiting time of all the machines.

The first line of input contains a single integer T, which is the number of test case. Each case starts with a line containing a single integer N (1 ≤ N ≤ 400), the number of nodes. The next line gives a list of N corrdinate of nodes. Each corrdinate is a integer in the range [-1000, 1000]. Consecutive integers are separated by a single space charcter. The repairman will depart from origin. Suppose he travels at unit speed.

For each case, output one line with the smallest sum of waiting time.

2
2
-1 2
3
-1 1 2

5
8

2009 Multi-University Training Contest 6 - Host by WHU