Write the function getCheapestRouteWithLayover(costCSV, fromCity, toCity) which determines the cheapest flight to get from one city to another
through a layover city. The function returns a tuple of the layover city and the cost of the two flights. See the example CSV for format of the string. Assume only valid input. If there is no way to get from the fromCity to the toCity with a layover, then return None.
CSV = """columbus,pittsburgh,240,berlin,70,paris,240,dayton,70
muenchen,pittsburgh,200,berlin,180,paris,300,dayton,200
pittsburgh,columbus,300,muenchen,160,berlin,120,dayton,250
dayton,paris,290,muenchen,230
berlin,pittsburgh,140,columbus,250,muenchen,100,paris,250,dayton,230
paris,pittsburgh,70,columbus,140,berlin,200,dayton,140"""
def processCSV(costCSV):
costDict = dict()
for rowString in costCSV.splitlines():
row = rowString.split(",")
fromCity = row[0]
rest = row[1:]
for i in range(0, len(rest), 2):
toCity, cost = rest[i], int(rest[i + 1])
if fromCity not in costDict:
costDict[fromCity] = dict()
costDict[fromCity][toCity] = cost
return costDict
def getCheapestRouteWithLayover(costCSV, fromCity, toCity):
costDict = processCSV(costCSV)
minLayoverCity, minCost = None, None
for layoverCity in costDict[fromCity]:
if toCity in costDict[layoverCity]:
cost = (costDict[fromCity][layoverCity] +
costDict[layoverCity][toCity])
if minCost == None or cost < minCost:
minLayoverCity, minCost = layoverCity, cost
if minLayoverCity == None:
return None
else:
return (minLayoverCity, minCost)
