-VIBE's blog

CSES Flight Discount

By -VIBE, history, 17 months ago, In English

Was solving this Cses problem from graph section.I came up with a dp approach for this but getting wrong answer on three testcases.Can anyone help me in where i am going wrong. Here is my submission

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

Comments Comments (8)
| Write comment?
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Flight discount is a template problem for this algorithm:

algorithm

I can't open Ideone links, could you use another method of sharing such as linking to your submission on cases or posting to Pastebin?

Given that the intended solution is the algorithm above, I'm not sure how you can solve it with a dp approach, but I am really interested to see your approach!

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your dp fails at this case

0 1 100
1 2 10
2 3 1
3 4 1
4 2 1
1 4 1
3 5 1

do[4][0] will be 1e18 instead of 3. Your dp fails on cycles, such as the example I gave. You need to run Dijkstra's algorithm to solve this problem. CP algorithms has a very good tutorial on it.

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

    His code may be wrong, but the test case you gave is running perfectly fine.

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

      It's numbered from 0 to n-1, but the problem gives numbers from 1 to n. If you add 1 to every element, his code outputs 62, which is incorrect, since there's a path that costs 54. Here's the fixed test case:

      6 7
1 2 100
2 3 10
3 4 1
4 5 1
5 3 1
2 5 1
4 6 1

      Here's an illustration fo the graph. You use the coupon on the edge from 1 to 2, then follow the path 1, 2, 5, 3, 4, 6.

      Image
      → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission getting TLE on Test 18 can someone help me with my code where can I optimize this code submission

mySubmission
→ Reply