Due to the installation of a new fire alarm in ITMO server room, the system may be occasionally unavailable on the 27-th of May between 06:00 and 15:00 (UTC). ×

kumarpratyush4's blog

By kumarpratyush4, history, 10 days 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

 
 
 
 

»
10 days 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!

  • »
    »
    10 days 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

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    also its still 10^6log wich should run

»
10 days 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).