Please answer in C++ A salesman wants to go to five different cities and sell some products. The location of the cities are listed in the following table.

City #	X_location	Y_location
City 1	1	1
City 2	1	3
City 3	4	1
City 4	5	3
City 5	3	5

The distance between two cities is defined as the Euclidean distance. That is:

Distance = sqrt( (x1 x2)^2 + (y1 y2)^2 )

For example the distance between cities 1 and 2 will be:

Distance = sqrt( (1 1)^2 + (1 3)^2 ) = sqrt( 5 ) = 2.236

The purpose: The salesman starts his journey from city 1. He then has 4 remaining options for the next city (city 2, city 3, city 4, city 5). If he chooses city 3 as the next destination, then he will have 3 remaining options (city 2, city 4, city 5). He wants to travel all the cities and then come back to the start location (City 1). Not all the paths will be a good choice. We want to help the salesman by finding the shortest path (best order of cities to visit starting from city 1).

Steps:

Step 1 [4 points]: Create a class City with x and y as the class variables. The constructor with argument will get x and y and will initialize the city. Add a member function getDistanceFrom() to the class that gets a city as the input and finds the distance between the two cities.

city1.getDistanceFrom(city2) will be distance between city 1 and 2.

Step 2 : Create 5 city objects and initialize their location (x and y) using the above table. Then put all of the five cities in a vector.

Step 3 [4 points]: Create a two dimensional array or vector DistanceVec of size 5 * 5 and initialize it such that DistanceVec[i,j] is the distance between city_i and city_j.

Step 4 [4 points]: If the salesman starts from the city 1, search all the possible paths and find the optimal path (order of cities to visit) that leads to the minimum total travel. Display the found optimal path (order of cities to travel) in your sample run.