第三十届国际大学生程序设计竞赛试题.pdf

Problem A Low Cost Air Travel Input File: air.in Air fares are crazy! The cost of a ticket is determined by numerous factors, and is usually not directly related to the distance traveled. Many travelers try to be creative, sometimes using only parts of tickets with stops in various cities to achieve lower-cost travel. However, the airlines are aware of this behavior, and usually require that the travel covered by a ticket be completed in order and without intervening travel. For example, if you have a ticket for travel from City-1 to City-2 then to City-3, you are not allowed to use only the portion of the ticket for travel from City-2 to City-3. You must always start at the first city on the ticket. In addition, you are not allowed to travel from City-1 to City-2, fly elsewhere and return, and then continue your journey from City-2 to City-3. Let’s consider an example. Suppose you are allowed to purchase three types of tickets: Ticket #1: City-1 to City-3 to City-4 $225.00 Ticket #2: City-1 to City-2 $200.00 Ticket #3: City-2 to City-3 $50.00 Suppose you wanted to travel from City-1 to City-3. There are two ways to get there using only the available ticket choices: Purchase Ticket #1 for $225.00 and use only the first leg of the ticket. Purchase Ticket #2 for $200.00 and Ticket #3 for $50. The first choice is the cheapest. Given a set of airline ticket offers, and one or more trip itineraries, you must determine how to purchase tickets in order to minimize the cost of travel. Each trip will be possible. Input Input consists of multiple test cases, each describing a set of ticket offers and a set of trip itineraries. Each case begins with a line containing NT, the number of