Delivery BoyProblem code: HOMDEL |
All submissions for this problem are available.
Chef has started Home Delivery scheme in one of his restaurants. As the scheme is new , Chef appoints only one employee to deliver food to various locations. The delivery boy who has been appointed is an absent-minded chap. He always forgets to fill fuel in his delivery scooter. So what he does is that whenever Chef sends him for delivery, he goes to the gas station from the restaurant first. He gets his tank filled and then he heads towards his destination. He will do this every single time irrespective of the destination. The delivery boy tries his best to be on time. And to do this, he will choose those paths(from restaurant to gas station AND gas station to destinaion) which cost him the least amount of time. Your task is to tell the Chef how much time can the delivery boy save if he had enough fuel in his scooter i.e. if he went to the destination directly without stopping for fuel (taking the path which costs him least amount of time).
The city has N streets numbered from 0 to N-1. The restaurant is on street number S, the gas station is on street number G and the food has to be delivered to street D . Note that S, G and D need not be distinct.
Input:
First line of the input contains a single integer N.Then follows an NxN matrix T which is represented in N lines with N space separated integers on each line.
T[i][j] denotes the time taken to move from the ith street to jth street. Obviously, T[i][i] = 0.
Next line contains a single integer M, the number of scenarios.
The following M lines contain 3 space separated integers S, G and D.
Output:
For each of the M scenarios, output the time taken by the delivery boy to deliver the food and the time he could have saved if he went directly from S to D.
Both these values must be on the same line separated by a single space.
Constraints:
1 ≤ N ≤ 250 1 ≤ M ≤ 10000 0 ≤ T[i][j] ≤ 100000 0 ≤ S,G,D ≤ N-1
Example:
Input:4 0 2 1 3 1 0 4 5 3 1 0 3 1 1 1 0 4 0 2 1 0 2 2 3 1 2 3 0 1Output:
2 0 1 0 3 2 3 2
| Author: | vamsi_kavala |
| Tester: | laycurse |
| Editorial | http://discuss.codechef.com/problems/HOMDEL |
| Date Added: | 1-07-2012 |
| 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, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
Is output for 3 1 2 correct
Output is correct. Hint: He
u are right suneetk92
is there any wrong with test
Maybe the input format should
@admin:Are the t[i][j]s
nothing wrong with test
@pratikjain1993 - If t[i][j]
@Admin My code is running
@admin can the "saved time"
@admin my code getting
T[i][j] > 0 for i not equal
Please someone clarify test
@mihsathe- since i,j will
foul!!!! kuruma solving it in
@kuruma: then whats the point
@makandriaco I am not solving
@ocozalp: It can't be...it
I am not able to understand
The time limit says 1sec ,
for the test case 3 1 2 even
T[i][j] can be 0 even if i !=
A lot of people are
@kuruma you were explaining
can anybody explain me the
>1s accepted
please provide some more test
can the boy take a path
Frustrating.. Everything
It will be better if details
M is more than 10000. use
I am new to codechef. I am
@anandveeramani : Nope, you
Hi, in the languages listed,
This is an interesting
can anyone clearly explain
does the boy take the
@ drpaulvazo : are you sure
@admin can i get all the set
the test case 3 1 2 seems to
@Admin, I an repeatidely
The hell is wrong with the
nooooooo, python solution get
Easy problem, but my solution
2 0 1 0 (3) 2 3 2 the
@Admin: whats going on for
i wrote a code for this
apply the shortest path