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.
Graph formed finally should be a tree. We connect all the other nodes to the node with smallest population which results in minimum cost.
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 (N-1) edges (which is known as a tree).
So we will be constructing a tree finally with (N-1) edges.
Suppose we create some random tree with (N-1) edges. Now I pick two nodes i and j where Pi and Pj both are not the minimum and remove that edge from there and connect nodes x and j, where Px is minimum.
I have a change of ( Px * Pj ) - ( Pi * Pj ) which is less than zero since Px < Pi.
So, we all nodes will be connected to the node with smallest value.
n=input value array=input ans=0 for i=1 to N-1: ans += value[i]*value print ans