This assignment involves implementing an adjacency list representation of a weighted graph, and using it to apply Dijkstra's shortest paths algorithm (single-source, all destinations) and MST algorithm to a weighted Problem Definition: In a city there are N farms, each of which is in need of a water supply. It costs w[i] Rials to build a well at farm i, and it costs c[i][j] to build a pipe in between farms i andj. A farm can receive water ifether theres well built there or there is some path of pipes to a farm with a well. Use the Dijkstra's shortest paths algorithm (SSAD) to find the lowest cost needed to build pipes from a given farm to every other farm Find the minimum amount of money needed to supply every farm with water, Design and implementation requirements The program will read the specification of the problem from an input file whose name will be given by the user. The input file will begin with two lines specifying the number of farms in the city, N, and the source farm. Each of those values will be preceded by a label that ends with a colon character :). The next line will ontain N values indicating the cost of building a well in each farm, followed by a blank line. The remainder f the file will be N lines, each containing N integer values for the cost of building pipes between the farms Costs will be integers in the range1 to 99. Missing pipes between farms will be designated by the value 0 Here's a sample: umber of farms: 11 Start farm: 94 73 87 The output consists of three sections, one displaying information about the given farms, the second displaying the results of running the Dijkstra's shortest paths (SSAD) algorithm, and the last displaying the minimunm amount of money needed The farms information display consists of two lines of labels (see sample, followed by N lines of output displaying the farms information in a format similar to the list of neighbors' structure. For each farm, there will be one row of data listing the farm number, followed by whitespace and a pipe symbol, followed by a list of neighbor records. A neighbor record consists of a neighbor (farm) number, followed by a colon character followed by the cost of building the corresponding pipe. Each integer in a neighbor record is written in a field of 3 columns. The farms information display is followed by a blank lin The SSAD results display begins with two lines of labels (see sample), followed by N lines showing the results for each possible destination farm (including the source farm itself). Each of these lines consists of three sections, the destination farm number, the lowest cost of building pipes found, and the actual path (a sequence of farm numbers separated by colon characters). If a farm is not reachable from the source farm display "inf" instead of the length. The: miniisplay rins wiih n linc; of lthl (x spllc by Nwing the: reesult This assignment involves implementing an adjacency list representation of a weighted graph, and using it to apply Dijkstra's shortest paths algorithm (single-source, all destinations) and MST algorithm to a weighted Problem Definition: In a city there are N farms, each of which is in need of a water supply. It costs w[i] Rials to build a well at farm i, and it costs c[i][j] to build a pipe in between farms i andj. A farm can receive water ifether theres well built there or there is some path of pipes to a farm with a well. Use the Dijkstra's shortest paths algorithm (SSAD) to find the lowest cost needed to build pipes from a given farm to every other farm Find the minimum amount of money needed to supply every farm with water, Design and implementation requirements The program will read the specification of the problem from an input file whose name will be given by the user. The input file will begin with two lines specifying the number of farms in the city, N, and the source farm. Each of those values will be preceded by a label that ends with a colon character :). The next line will ontain N values indicating the cost of building a well in each farm, followed by a blank line. The remainder f the file will be N lines, each containing N integer values for the cost of building pipes between the farms Costs will be integers in the range1 to 99. Missing pipes between farms will be designated by the value 0 Here's a sample: umber of farms: 11 Start farm: 94 73 87 The output consists of three sections, one displaying information about the given farms, the second displaying the results of running the Dijkstra's shortest paths (SSAD) algorithm, and the last displaying the minimunm amount of money needed The farms information display consists of two lines of labels (see sample, followed by N lines of output displaying the farms information in a format similar to the list of neighbors' structure. For each farm, there will be one row of data listing the farm number, followed by whitespace and a pipe symbol, followed by a list of neighbor records. A neighbor record consists of a neighbor (farm) number, followed by a colon character followed by the cost of building the corresponding pipe. Each integer in a neighbor record is written in a field of 3 columns. The farms information display is followed by a blank lin The SSAD results display begins with two lines of labels (see sample), followed by N lines showing the results for each possible destination farm (including the source farm itself). Each of these lines consists of three sections, the destination farm number, the lowest cost of building pipes found, and the actual path (a sequence of farm numbers separated by colon characters). If a farm is not reachable from the source farm display "inf" instead of the length. The: miniisplay rins wiih n linc; of lthl (x spllc by Nwing the: reesult