Congratulations, you’ve landed a paid co-op position and can start working on gaining work experience and paying off all of those student loans... but the job is far, and air travel is expensive. Looking to squeeze a few extra dollars in savings, the quest is to find the cheapest possible flight, even if that requires multiple connections.
The flight search is to go from YYZ to SEA.
The input file DATA5.txt will contain 5 sets of input. Each set starts with an integer 1 < N ≤ 20 – the size of the available data. This is followed by N lines describing the available flights, in the form of CODE1 CODE2 price. Codes are 3-character-long airport codes, and the prices are positive integer values.
The output file OUT5.txt will contain 5 lines, which are integer values for the cheapest total flights for each scenario.
Note: There will always be a possible flight path.
Note 2: The flights are described in a single direction. That is, “SEA YYZ 1” cannot be taken to go from YYZ to SEA.
1
YYZ SEA 500
3
YYZ SEA 500
YYZ YVR 300
YVR SEA 100
500
400