This is the program with input file on page 2.

And below are the sample codes for minimum spanning tree from which we have to write the code for the above program.

Program 8: Snow Routes 1 Goals. To adapt and reuse my graph demo program . To use a vector and its sort algorithm. 2 Overview The East Dakota Department of Highways is examining the weather forecast for the coming winter, and it doesn't look good. Heavy snows are expected much of the winter, which means keeping roads clear will be a challenge. The Department plans to designate some roads as Snow Routes. These roads will have priority for snow removal. It is vital that all cities have at least one Snow Route, and that it is possible to go from any city to any other city via Snow Route roads. The Highway Department wants to identify the minimum road length needed to ensure all cities are connected via Snow Routes. 3 Instructions: Due November 27 The input file, snow.in.txt, contains a list of major highways that connect twelve cities. Use a vector to store the set of roads. Each road is listed as a starting city, an ending city, and the length of the road in miles (an integer 0). All roads are two-way. There may be multiple roads between some cities. Roads are not listed in any particular order, so you will need to sort them Implement one of the graph algorithms we have studied to solve this problem. Start with my graph program, then add to it and/or modify it, as needed. Your output must give a set of Snow Routes that connect all twelve cities, and the total length of those roads. Edmonds Grant Denslow Billings Frankston Aberdeen Denslow Grant Carston Aberdeen Billings Frankston Aberdeen Denslow Carston Grant Denslow Grant Billings Aberdeen Aberdeen Carston Billings Aberdeen Edmonds Billings Carston Denslow 51 42 37 64 65 48 49 58 59 46 69 29 37 31 42 60 32 12 41 30 40 27 26 31 26 51 anssen Ketchikan anssen Hammond anssen Edmonds Hammond anssen Hammond Grant Grant Ketchikan Landry Melville Landry Melville Grant Hammond Landry 11ings Carston Edmonds Frankson Ketchikan Grant Melville Grant Ketchikan Grant 3 49 36 Denslow string fileType; string tail, head; int weight; Node* fromNode; I/Point to a node in the nodemap. Node* toNode; getline( in, fileType; cout > tail >> head >> weight; if (in.eof)) break; /7If the starting node is NOT in the graph, add it. fromNode makeNode (tail); // find node with 1nput name in node list toNodemakeNode (head) / and create a node if none exists 23 24 25 26 27 28 29 Construct edge and put on adjacency list of both nodes Edge* ed - new Edge(fromNode, toNode, weight); edgeList.push_back ed ); fromNode->addEdge( *ed ); toNode->addEdge( *ed ); 31 Node* Graph::makeNode (string name) t 32 mapsecond; Node* ndnew Node name); it - nodeMap.begin); nodeMap.insert( it, pairname, nd)); return nd; //Pointer to named node name not found in map 35 36 37 // Display on the screen a list of nodes in the graph. 38 / Each node name is followed by the list of edges that start at that node. 39 ostream& Graph::print (ostream& out) f 40 41 42 43 out : :iterator walker; for (walker-nodeMap.begin) walker nodeMap.end ); ++walker) Node* np = walker-> second; out > tail >> head >> weight; if (in.eof)) break; /7If the starting node is NOT in the graph, add it. fromNode makeNode (tail); // find node with 1nput name in node list toNodemakeNode (head) / and create a node if none exists 23 24 25 26 27 28 29 Construct edge and put on adjacency list of both nodes Edge* ed - new Edge(fromNode, toNode, weight); edgeList.push_back ed ); fromNode->addEdge( *ed ); toNode->addEdge( *ed ); 31 Node* Graph::makeNode (string name) t 32 mapsecond; Node* ndnew Node name); it - nodeMap.begin); nodeMap.insert( it, pairname, nd)); return nd; //Pointer to named node name not found in map 35 36 37 // Display on the screen a list of nodes in the graph. 38 / Each node name is followed by the list of edges that start at that node. 39 ostream& Graph::print (ostream& out) f 40 41 42 43 out : :iterator walker; for (walker-nodeMap.begin) walker nodeMap.end ); ++walker) Node* np = walker-> second; out