kumarpratyush4's blog

help in 1063 B
By kumarpratyush4, history, 5 years ago, In English

https://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

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

»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    if the lft moves are optimized so are the right ones because they are linear to each other for any cell

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

    also its still 10^6log wich should run

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

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

→ Reply