Please solve it eith Java. In this homework, you must implement your own graph data structure by taking inspiration from your

textbook and use it to help to solve problem. You are not allowed to use any external library or jar file.

Any solutions without using graph data structure are not evaluated!

Q$1(50$ points$)$:

Imagine you established a new electricity distribution company. For each $10km,$ you should use

one electricity pole and you should use the minimum number of poles that will provide

electricity to cities you are responsible for. For this reason, you need to create a kind of map.

The inpul.lxl file given to you contains the name and coordinates $(x$ and $y,$ respectively$)$ of the

cily. Fxample inpul. Ixt is as follows:

$A,2,2$

$B,3,5$

$C,5,5$

$D,-1,2$

$E,3,0$

You should read inpul. $x1$ lile, and construct your graph based on this information. For example,

the first line means that City $A$ is on coordinate $x2$ and $y2,$ or the second line means that City

$13$ is on coordinate $x-3,y.$

You can assume that there is always a path between any two cities and you should use

Euclidian distance to calculate length of this path. For example, there is a path from cities D to

$E$ and $E$ to $D.$ Their lengths are equal to

$\sqrt[\phantom{2}]{(-1-0{)}^2+(2-3{)}^2}\sqrt[\phantom{2}]{2}$

Example visualization of citics and paths are as follow for input.txt:

Your goal is to find paths to provide electricity to all cities and require the use of the least

number of poles. While printing, you should print the path in aseending order of their length.

Also, your path starts with city which comes from alphabctically first.

Here is example input and output: Input.txt $//$ you should read $.$txt file name from the user

Paths are: $//$ you should print shortest path first. And path should start with

B$-$C: $2\mathrm{.}0//$ city name which comes from alphabetically first.

A$-$E: $2\mathrm{.}2$

A$-$D: $3\mathrm{.}0$

A$-$B: $3\mathrm{.}2$