hyman00's blog

By hyman00, history, 2 months ago, In English

In this problem, we need to calculate the shortest path from an origin in a graph with up to $$$10^5$$$ nodes.

The real solution is using dijkstra and priority queue.

But some participants used spfa which can be $$$O(n^2)$$$ in some special datas Like this submission.

Our IOI aker PEIMUDA made two datas

24999 99999 25000

33332 99998 33333

The answers are



They can make the submisssion run up to 5 seconds.

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

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

I hope someone can add these datas and rejudge the problem.