arnav2004's blog

By arnav2004, history, 2 years ago, In English

I was solving this problem on the CSES Problemset Longest Flight Route.

Here is my code

The code is getting Accepted in all but 2 testcases(TLE in those 2) .

I cannot debug with those testcases since they are HUGE.

I reckon that the problem is in my BFS Code but I can't seem to find why it would go in an infinity loop.

If anyone could provide a testcase or something it would be incredibly helpful.

Thanks.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

BFS only runs in $$$O(m)$$$ when you're looking for the shortest path. As an example of why your code is slow, it runs in $$$O(n^2)$$$ on the following test case:

Test case