Minimum Chain Joining Cost

Problem Statement

Minimum Chain Joining Cost Problem Description There is a large broken chain (think of Ship Anchor Chain) with N pieces. Join all the pieces to make chain whole again. Process to join chain is as follows: Pick any two pieces and join those. Repeat this process until all pieces are joined. Each join operation requires some cost (labour cost, welding cost etc.). Cost of each join operation is equal to sum of the Weights W of pieces which are being joined. Total cost will be sum of costs each step. Find the way to keep total cost as minimum. Input: Value of N in 1st line. Comma and space separated N integers in 2nd line, which denote individual weights of N pieces. Output: Value of minimum total cost. Examples Example 1: Input: 4 8, 2, 3, 4 Output: 31 Explanation: In the above sample, a broken chain has 4 pieces with given weights. Two pieces are joined at a time, for example if 8 and 2 are joined, a new piece will have weight of 10. Then it can be joined with any of the remaining pieces