DWITE Online Computer Programming Contest, April 2010, Problem 5
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
The input will contain 5 sets of input. Each set starts with an integer — size of available data, followed by lines describing the available flights, in the form of
CODE1 CODE2 price. Codes are 3 character long airport codes, the prices are positive integer values.
The output will contain 5 lines, 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 can not be taken to go from
1 YYZ SEA 500 3 YYZ SEA 500 YYZ YVR 300 YVR SEA 100