### Death_Scythe's blog

By Death_Scythe, history, 9 years ago,

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!

• 0

| Write comment?
 » 9 years ago, # |   0 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 5So if u do greedy, u end up taking 11 hours instead of 8
•  » » 9 years ago, # ^ |   0 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.
•  » » » 9 years ago, # ^ |   0 Can you please let me know where's the error in code? Thanks!
 » 9 years ago, # |   0 Can anyone please help me out with this? I still do not see the error. Many thanks!
 » 9 years ago, # |   0 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.