Christina is searching for a new job. She lives in Shreveport, Louisiana, and has interviews in Barrow, Alaska; Tucson, Arizona; and Rochester, New York. The costs of the one-way flights between these four cities are as follows: Shreveport to Barrow costs $855, Shreveport to Tucson costs $803, Shreveport to Rochester costs $113, Barrow to Tucson costs $393, Barrow to Rochester costs $337, and Tucson to Rochester costs $841.

(a) Represent this traveling salesman problem with a complete, weighted graph showing the prices of the flights on the appropriate edges. 

(b) Use the brute force method to determine the least expensive route for Christina to travel to each city and return home to Shreveport. 

(c) What is the minimum cost she can pay?