All submissions for this problem are available.
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.
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.
For each case, output the minimum fuel consumed so that pizzas are delivered to all the houses prefixed by “Case #X:”
Input 1 40 40 3 0 0 0 1 20 0 1 1 1 25 1 1 1 2 30 Output 75
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, 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, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.