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!
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->Dand another path beA->C->D. So lets say u start at hour 1, and at hour 1, weight ofA->B is 1, while weight ofA->C is 3. Let at hour 2, weight ofB->D is 10and at hour 3, weightC->D is 5So if u do greedy, u end up taking 11 hours instead of 8
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.
Can you please let me know where's the error in code? Thanks!
Can anyone please help me out with this? I still do not see the error. Many thanks!
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.