AdnanShamsi's blog

CSES PROBLEM: FLIGHT DISCOUNT...help needed
By AdnanShamsi, history, 4 years ago, In English

https://cses.fi/problemset/task/1195 to solve this problem I implemented dijkstra but i am getting wrong answer on test case on test case 7 and 14 .Those test cases are very big hence i am unable to debug with those test cases. Can anyone give me small test cases where my code fails,or any suggestion of why it is failing .Here's my code https://pastebin.com/u08T3SJq .Thanks in advance

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

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Your logic of handling the cupon looks wired.

There are basically two options:

We can maintain two dist arrays (ie add one dimension), one array for "cupon used", the other one for "not used so far", and use more or less simple dijkrsta.

The other option is create two distance arrays, one for dist from start, one for dist from destiny, both without using coupon. Then combine those two arrays by using the coupon on one flight "between" them.

Note that at cses you can download big testcases, too.

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

    thanks a lot your logic is far more better and easy to code than mine's

    → Reply