### hyman00's blog

By hyman00, history, 2 months ago,

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

1000000000000000000
24999 99999 25000

1000000000000000000
33332 99998 33333


999999999687537499

999999999444505554


They can make the submisssion run up to 5 seconds.

• +10

 » 2 months ago, # |   0 I hope someone can add these datas and rejudge the problem.