### PROBLEM LINK:

**Author:** Shiplu Hawlader

**Tester:** Tasnim Imran Sunny

**Editorialist:** Lalit Kundu

### DIFFICULTY:

SIMPLE-EASY

### 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 (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 P_{i} and P_{j} both are not the minimum and remove that edge from there and connect nodes x and j, where P_{x} is minimum.

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.

Pseudo Code:

```
n=input
value array=input
ans=0
for i=1 to N-1:
ans += value[i]*value[0]
print ans
```

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.