C - 災害に強い通信ネットワーク 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

東西に伸びる一本道に沿って N 個の都市があります。i 番目の都市は西端から距離 X_i の位置にあります（都市は必ずしも西から東の順に番号付けされているとは限りません）。

高橋君はこれらの都市間に双方向の通信回線を敷設し、災害に強い通信ネットワークを構築しようとしています。通信回線は任意の2都市間に直接敷設でき、都市 i と都市 j の間に通信回線を敷設するコストは |X_i - X_j| です。ただし、次の条件があります。

  • 同じ2都市間に複数の通信回線を敷設することはできない。
  • 各通信回線はその両端の2都市のみを接続する。地理的に2都市の間に位置する他の都市であっても、その回線には接続されない。

構築するネットワークは、次の災害耐性条件を満たす必要があります。

  • 任意の 1 つの都市 v を選んだとき、都市 v およびその都市 v に直接接続するすべての通信回線をネットワークから取り除いても、残りのすべての都市が互いに通信できる。

ここで「互いに通信できる」とは、残りの都市と残りの通信回線からなるネットワークにおいて、任意の2都市間で、直接の通信回線または他の都市を中継してたどることで到達可能であることを意味します。

この条件を満たすネットワークを構築するために必要な通信回線の敷設コストの総和の最小値を求めてください。

制約

  • 3 \leq N \leq 10^6
  • 0 \leq X_i \leq 10^9
  • X_i \neq X_j (i \neq j)
  • 入力はすべて整数

入力

N
X_1 X_2 \cdots X_N
  • 1 行目には、都市の個数を表す整数 N が与えられる。
  • 2 行目には、各都市の西端からの距離を表す整数 X_1, X_2, \ldots, X_N がスペース区切りで与えられる。

出力

条件を満たすネットワークを構築するために必要な敷設コストの総和の最小値を整数で出力してください。

入力例 1

4
0 2 5 9

出力例 1

18

入力例 2

5
10 1 7 3 20

出力例 2

38

入力例 3

10
42 5 100 17 63 88 29 74 1 56

出力例 3

198

入力例 4

25
1000 250 4300 120 9800 7600 3150 640 8750 5200 60 7000 1500 2400 9999 3600 8100 4700 5900 9300 2050 6800 7350 1110 5550

出力例 4

19878

入力例 5

3
0 1000000000 500000000

出力例 5

2000000000

Score : 366 pts

Problem Statement

There are N cities along a straight road running from west to east. The i-th city is located at distance X_i from the western end (the cities are not necessarily numbered from west to east).

Takahashi is trying to build a disaster-resistant communication network by installing bidirectional communication lines between these cities. A communication line can be installed directly between any two cities, and the cost of installing a communication line between city i and city j is |X_i - X_j|. However, the following conditions apply:

  • Multiple communication lines cannot be installed between the same pair of cities.
  • Each communication line connects only the two cities at its endpoints. Even if another city is geographically located between the two cities, it is not connected to that line.

The constructed network must satisfy the following disaster resilience condition:

  • For any single city v, even if city v and all communication lines directly connected to city v are removed from the network, all remaining cities can still communicate with each other.

Here, "can communicate with each other" means that in the network consisting of the remaining cities and remaining communication lines, any two cities can be reached from one another either through a direct communication line or by relaying through other cities.

Find the minimum total cost of installing communication lines needed to construct a network satisfying this condition.

Constraints

  • 3 \leq N \leq 10^6
  • 0 \leq X_i \leq 10^9
  • X_i \neq X_j (i \neq j)
  • All inputs are integers

Input

N
X_1 X_2 \cdots X_N
  • The first line contains an integer N representing the number of cities.
  • The second line contains integers X_1, X_2, \ldots, X_N separated by spaces, representing the distance of each city from the western end.

Output

Output as an integer the minimum total installation cost needed to construct a network satisfying the condition.

Sample Input 1

4
0 2 5 9

Sample Output 1

18

Sample Input 2

5
10 1 7 3 20

Sample Output 2

38

Sample Input 3

10
42 5 100 17 63 88 29 74 1 56

Sample Output 3

198

Sample Input 4

25
1000 250 4300 120 9800 7600 3150 640 8750 5200 60 7000 1500 2400 9999 3600 8100 4700 5900 9300 2050 6800 7350 1110 5550

Sample Output 4

19878

Sample Input 5

3
0 1000000000 500000000

Sample Output 5

2000000000