Death_Scythe's blog

Google APAC Round B — Travel
By Death_Scythe, history, 9 years ago, In English

Hello all! I was trying to solve this problem from the recent APAC contest: https://code.google.com/codejam/contest/10214486/dashboard

I think this problem can be solved by dijkstra's shortest path algorithm. I precompute the minimum time taken from the source for every value of S so that the queries can be answered in constant time.

Here's my code: http://ideone.com/cle94b

I don't see why I am getting a WA.

Any help is appreciated. Thanks!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

u need dp with dijsktra, it cant be done with greedy. Lets say, i have to go from A to D. let path be A->B->D and another path be A->C->D. So lets say u start at hour 1, and at hour 1, weight of A->B is 1, while weight of A->C is 3. Let at hour 2, weight of B->D is 10 and at hour 3, weight C->D is 5

So if u do greedy, u end up taking 11 hours instead of 8

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think u are wrong because we will keep on adding until D is popped from the priority queue which will make our answer 10 even for greedy.

    PS : I did it using greedy and got the correct answer.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please let me know where's the error in code? Thanks!

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please help me out with this? I still do not see the error. Many thanks!

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You don't seem to be updating the time in your dijkstra code. When you start off from vertex 1 at time x(using the parameter in your code), you reach the next vertex v at some time T=(x+t)%24 (where t is the weight of the path from 1 to v at time x), and when you start off from the next vertex, you need to use this new time T, not the old time x, because the weight of the roads changes based on this. Your code seems to treat this x as constant throughout one run of dijkstra, which is wrong.

→ Reply