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 by god_no_plz_no.
defrong made two datas
1000000000000000000
24999 99999 25000
1000000000000000000
33332 99998 33333
The answers are
999999999687537499
999999999444505554
They can make the submisssion run up to 5 seconds.
