Lance is searching for a new job. He lives in Portland, Oregon, and has interviews in Des Moines, Iowa; Charleston, West Virginia; and Montgomery, Alabama. The costs of the one-way flights between these four cities are as follows: Portland to Des Moines is $428, Portland to Charleston is $787, Portland to Montgomery is $902, Des Moines to Charleston is $449, Des Moines to Montgomery is $458, and Charleston to Montgomery is $415. 

(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 ex-pensive route for Lance to travel to each city and return home to Portland.

(c) What is the total cost of airfare for Lance’s trip in part (b)?