1802: Graph Theory Homework

There is a complete graph containing n vertices, the weight of the i-th vertex is w i .
√
The length of edge between vertex i and j (i ̸ = j) is ⌊ |w i − w j |⌋.
Calculate the length of the shortest path from 1 to n.

The first line of the input contains an integer T (1 ≤ T ≤ 10) denoting the number of test cases.
Each test case starts with an integer n (1 ≤ n ≤ 10 5 ) denoting the number of vertices in the graph.
The second line contains n integers, the i-th integer denotes w i (1 ≤ w i ≤ 10 5 ).

For each test case, print an integer denoting the length of the shortest path from 1 to n.

1
3
1 3 5

2