PROBLEM LINK:Author: Shiplu Hawlader DIFFICULTY:SIMPLEEASY PREREQUISITES:PROBLEM:Connect all the N(<=10^5) cities to make a connected graph in minimum cost. Cost of adding each edge is product of population of the two cities between whom edge is being added. All populations are given in the input. QUICK EXPLANATION:Graph formed finally should be a tree. We connect all the other nodes to the node with smallest population which results in minimum cost.
EXPLANATION:We need to add edges such that all the cities become connected. Connected is defined as "it should be possible from any city to reach any other city by a sequence of edges". There doesn't exist a graph which is connected and has less than (N1) edges (which is known as a tree). I have a change of ( P_{x} * P_{j} )  ( P_{i} * P_{j} ) which is less than zero since P_{x} < P_{i}.
So, we all nodes will be connected to the node with smallest value.
AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 17 Feb '14, 00:14

@kuldeep992: You should have used long to avoid integer overflow. answered 17 Feb '14, 00:37

http://www.codechef.com/viewsolution/3429768 Why it got wrong? answered 17 Feb '14, 03:05

can anyone explain me where is integer overflowing in my code ? http://www.codechef.com/viewplaintext/3426847 answered 18 Feb '14, 16:46

to avoid integer overflow use ' long long ' . I had got a WA while using 'int' . and the problem is of 'adhoc ' category which means you do not require to apply any special algorithm to get it solved . answered 14 Jan '16, 13:31

please explain the case n=1...why isn't the ans=0 for that? answered 11 Feb '16, 23:04

why can't we use long n, long vector and long long sum?? answered 29 May '17, 16:35

can you tell me why i got wrong answer... http://www.codechef.com/viewsolution/3428578
http://www.codechef.com/viewsolution/3427213
sme here!! can u tell d reson 4r it's faliure?