About GYM100078E

Revision en1, by hyman00, 2022-12-02 08:54: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 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.

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)