All submissions for this problem are available.
Delhi tour operators offer attractive tour options with low cost tickets. Tickets are
made available to interested tourists for visits to tourist spots in the city, following
certain routes, under certain conditions.
The conditions are illustrated through some examples. A ticket to visit Spot-1, then
Spot-2 and then Spot-3, does not allow a tourist to use only the portion of the ticket for
visiting Spot-2 first and then Spot-3. A tourist must always start at the first spot
mentioned on the ticket. In addition, tourists are not allowed to utilize the ticket to
visit Spot-1 and Spot-2 in order, have a break to visit other spots using different
tickets and on return to Spot-2 continue visit from Spot-2 to Spot-3 using the same
ticket. Suppose three types of tickets are available:
Ticket #1: Spot-1 to Spot-3 to Spot-4 at a cost of Rs225
Ticket #2: Spot-1 to Spot-2 at a cost of Rs200
Ticket #3: Spot-2 to Spot-3 at a cost of Rs50
For a tourist having a plan to visit Spot-1 and then Spot-3 there are two options of
Have Ticket #1 for Rs225 and use it only for the first leg of the ticket.
Have Ticket #2 for Rs200 and Ticket #3 for Rs50.
Obviously, for the specified plan, the first option has the minimum cost of tickets.
Given a set of ticket options, and one or more visit plans, you must determine, for each
visit plan, the minimum cost of tickets.
Input consists of multiple test cases.
Each case begins with a line containing T, the number of ticket options, followed by T
options, one to a line. Each option consists of a positive integer specifying the cost of
the ticket, the number of tourist spots in the ticket's route, and then that many spots.
Each spot in a case has an arbitrary, but unique, integer identification number.
The next line contains P, the number of plans for which the minimum cost of tickets is to
be found. P lines follow, giving the route for each plan. Each line consists of the number
of spots in the plan (including the starting spot) followed by that many spot
identification numbers, given in the order they are to be visited.
There will be no more than 20 ticket options or 20 visit plans in a test case. Each ticket
option and visit plan lists from 2 to 10 spots. No ticket cost exceeds Rs5000. Adjacent
spots in a route or plan will be distinct. Options and plans are numbered sequentially in
each set, starting with 1.
The last case is followed by a line containing a zero.
For each visit plan, output one line containing the case number, the plan number, the
minimum cost of the plan, and the numbers of the ticket options used for the plan, in the
order they will be used. Follow the output format shown below. The output will always be
Input: 3 225 3 1 3 4 200 2 1 2 50 2 2 3 1 2 1 3 3 100 2 2 4 100 3 1 4 3 200 3 1 2 3 2 3 1 4 3 3 1 2 4 0 Output: 1 1 225 1 2 1 100 2 2 2 300 3 1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.