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

help in 1063 B
Автор kumarpratyush4, история, 6 лет назад, По-английски

https://mirror.codeforces.com/problemset/problem/1063/B this question can be done with djikstra as well. but dont know y its giving TLE. https://ideone.com/Az9ZAL (its properly commented -running and no templates are used so wont be tough to read) .using djikstra i am assigning 1 unit weight to all the left edges. if anyone can suggest any optimization i would be very thankful. UPD-error found i was putting less than -equal sign for checking djikstra

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

First, if you run a Dijkstra you are using a priority queue, that adds a "log" to your time complexity and it isn't necessary because no shortest paths are needed, you just have to count how many cells you can reach, so you could do it with a normal BFS.

Second, the problem have constraints on the left and right moves.

Edit:

My comment is wrong, since you want to get to each cell with the least amount of work. You do need to use a shortest path algorithm!

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by kumarpratyush4 (previous revision, new revision, compare).

→ Ответить