Pizza TroubleProblem code: MANIP6 |
Thank The Lord for Vai's Pizza on Planet Fenderland. The houses in Fenderland are all placed on a grid of roads thanks to the idealism of Mr. Lifeson. Every intersection between a pair of roads is denoted by a pair of co-ordinates (x,y). Vai's Pizza is at (0,0) on the grid. As with all pizza houses, Vai's Pizza delivers pizzas to your home for free and has employed delivery boys for the same. When a delivery boy sets out, he is given a list of the houses to deliver pizzas to. Transport vehicles in Fenderland are pollution free and travel close to the speed of light on account of using the Gramm brand of fuel. So the delivery boy doesn't have the 35 minutes or free deadline breathing down his neck. But there's a catch. Gramm fuel is pretty costly and he would be penalised if he over-consumes. Not the ones to be outsmarted, the delivery boys have made a record of the fuel consumed while driving between quite a few points in the town and use it for reference whenever they have a delivery to make. Help the delivery boy make a wise decision of choosing the right path that doesn't put his neck on the guillotine.
Input
The first line will have N, the number of test cases. The next line contains m and n where (m,n) is the co-ordinate of the end of the grid. The next line gives d, the number of houses to deliver pizzas to followed by d lines of the form x y u v w where (x,y) and (u,v) are two points on the grid and w is the fuel consumed between them.
Output
For each case, output the minimum fuel consumed so that pizzas are delivered to all the houses prefixed by Case #X:
Sample
Input 1 40 40 3 0 0 0 1 20 0 1 1 1 25 1 1 1 2 30 Output 75
| Author: | admin |
| Date Added: | 31-08-2009 |
| Time Limit: | 1 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Change the example output ..
Change the example output .. Shouldn't it be Case#X:75
hi, The output does not
hi,
The output does not have "Case #X". Just the result.
regards,
Ankur
So why does the output
So why does the output section say 'For each case, output the minimum fuel consumed .. prefixed by Case #X'? ;)
hi, Stephen: its a mistake
hi,
Stephen: its a mistake in the problem statement. Again, there is no "Case #X" in the output.
regards,
Ankur (event co-ordinator)
what r the limits on d?
what r the limits on d?
It will fit within 32 bits,
It will fit within 32 bits, that's guranteed :)
It will fit within 32 bits,
It will fit within 32 bits, that's guranteed :)
It will fit within 32 bits,
It will fit within 32 bits, that's guranteed :)
It will fit within 32 bits,
It will fit within 32 bits, that's guranteed :)
It will fit within 32 bits,
It will fit within 32 bits, that's guranteed :)
It will fit within 32 bits,
It will fit within 32 bits, that's guranteed :)
It will fit within 32 bits,
It will fit within 32 bits, that's guranteed :)
It will be within 232-1,
It will be within 232-1, that's for sure :)
Sorry for too many comments.
Sorry for too many comments. Some problems with the network connection here, hit refresh excessively
Do we have to calculate the
Do we have to calculate the return cost as well
As in does the pizza boy have to come back to (0,0)
Ayushman