Chef and Kingship
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Chef is the new king of the country Chefland. As first and most important responsibility he wants to reconstruct the road system of Chefland. There are N (1 to N) cities in the country and each city i has a population Pi. Chef wants to build some bi-directional roads connecting different cities such that each city is connected to every other city (by a direct road or through some other intermediate city) and starting from any city one can visit every other city in the country through these roads. Cost of building a road between two cities u and v is Pu x Pv. Cost to build the road system is the sum of cost of every individual road that would be built.
Help king Chef to find the minimum cost to build the new road system in Chefland such that every city is connected to each other.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
First line contains an integer N denoting the number of cities in the country. Second line contains N space separated integers Pi, the population of i-th city.
For each test case, print a single integer, the minimum cost to build the new road system on separate line.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 1 ≤ Pi ≤ 106
Input: 2 2 5 10 4 15 10 7 13 Output: 50 266
|Tags||ad-hoc, cook43, graph, shiplu, simple|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.