Блог пользователя Death_Scythe

Автор Death_Scythe, история, 9 лет назад, По-английски

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
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 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 5

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 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.