Sumanto's blog

By Sumanto, 4 years ago, In English

https://cses.fi/problemset/task/1195 to solve this problem i implemented dijkstra's and Dynamic Programming to decide whether to opt for coupon or not for each state transiton.But I'am getting TLE and not able to optimize my code. I think my approach is slow. Any suggestion please help. Here is william lin's code https://youtu.be/dZ_6MS14Mg4?t=13603 but i did't get his approach. If any one could explain what he did will be helpful

My Code
  • Vote: I like it
  • -2
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 6   Vote: I like it +5 Vote: I do not like it

Here's my approach...

-Firstly find shortest path from 1 to every node. (answers in array A)

-Then find shortest path from N to every node (on Inverted graph) which means finding shortest path from every node to N.(answers in array B)

-Then consider each edge(u,v) in graph , suppose you are applying discount on that edge... then if we can reach 1 to u and N to v (in short v to N) then ans=min( ans , A[u] + weight/2 + B[v] )...

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    @Kartik_Bhanderi

    Thanks for your input. I tried following your approach and wrote the following code:

    My code

    However, I still seem to get TLE on the majority of test cases. Is this only because I've implemented Bellman-Ford instead of Dijkstra or would you refactor my current code to be more efficient?

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 5   Vote: I like it +2 Vote: I do not like it

      Firstly put your code in spoiler properly. (for that choose spoiler and inside that choose block and place your code there...)

      Like this

      And as you said you have implemented bellmen ford , whose time complexity is O(V.E) , so obviously it will result into TLE.

      And in our case we only need single source shortest path , hence no need to use bellman ford instead we can use dijkstra's algo.

      Hope it helps ;)

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Sorry about that; I've fixed the formatting now.

        And yes, I thought so too. Thanks for the confirmation. I'll try to learn Dijkstra's and implement it now!

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it +2 Vote: I do not like it

          Good.

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

            Hi Kartik_Bhanderi I got TLE in 4 cases by using Dijkstra too!

            Can you please check if anything went wrong?

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

              Why do you put the array (node,distance) in the priority queue, shouldn't it be the other way around to correctly sort distance first? I think that could be your problem.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it
              • Use long long only when it's needed
              • Try scanf to take input

              Your logic also seems to be wrong, in priority queue it shoud be (dist,node).

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

    Sir, can you please explain what is 'u' and what is 'v'?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Both represent Node.

      From answer's context : there is an edge between node u and node v.

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

I got same aproach as yours, but use priority_queue instead of set. And I do not erase any extra element from the queue at any time. Just put new vertex on the queue whenever one of the dp-values becomes smaller.

Spoiler
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    By adding negative values of DP you are priority queue work as min_heap?

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

      Yes, this is just to make the priority_queue.top() work like set.begin(), ie return the smallest element.

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

        Is it safe to assume that set operations are more expensive than operations on priority queue?

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

          Yes, of course, especially write access is more expensive. Same O(logn), but bigger constant factor.