About GYM100078E

Revision en2, by hyman00, 2022-12-02 09:07:33

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.

The alt of PEIMUDA 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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English hyman00 2022-12-02 09:08:07 18 Tiny change: '4796).\n\nThe alt of [user:pei' -> '4796).\n\nOur IOI aker [user:pei'
en2 English hyman00 2022-12-02 09:07:33 63
en1 English hyman00 2022-12-02 08:54:33 643 Initial revision (published)