DWITE '09 R6 #5 - Air Travel Planning

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 64M
Problem type
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 YYZ to SEA.

The input will contain 5 sets of input. Each set starts with an integer 1 \le N \le 20 — size of available data, followed by N 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 YYZ to SEA.

Sample Input

1
YYZ SEA 500
3
YYZ SEA 500
YYZ YVR 300
YVR SEA 100

Sample Output

500
400

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments


  • 0
    dawangk  commented on Dec. 13, 2018, 11:25 p.m. ← edited

    The problem said that: The output will contain 5 lines, integer values for the cheapest total flights for each scenario.

    But the output for the sample input #1 have only 2 lines


    • 1
      Rimuru  commented on Dec. 14, 2018, 1:25 a.m. ← edited

      For the sample, they only provide 2 sets of data.


  • 2
    loltrollkill  commented on Dec. 9, 2018, 10:33 p.m. ← edited

    Is the input 2 sets or 5 sets? Should I follow the problem description or should I follow the sample?


    • 3
      Rimuru  commented on Dec. 10, 2018, 2:49 a.m.

      Similar to other DWITE problems, this one also requires 5 sets of input.