Chef Under Pressure

general
,
1

qstn http://www.codechef.com/DEC14/problems/CHEFPRES

can anyone explain test case 7(8 3)

i think answer should be 3 instead of 1 as distance is maximum from node (8 to 3) than node (8 to 1)

1 Like
2

According to comments, the condition is wrong:

Chef wants to travel to the city C such that:

  • F©=P
  • There is no other city D having F(D)=P and G(D) < G©.

Above this is:

Chef wants to stay as far as possible from the capital city (numbered B) during his travels.

So correct condition should be:

There is no other city D having F(D)=P and G(D) > G(C)

I checked it and I agree with you, that answer should be 31.

edit: description above

1 Like
3

In both cases, since the trip starts from the capital, G(1) = G(3) = 0. So you need to choose the one with the smallest number (in this case city 1). Hope this helps :smiley:

3 Likes
4

I agree, finally I understood first test case correctly also

let G(i) be the smallest distance between B and any city on the unique path connecting cities A and i

I had to read this several times…