Обсуждение @ 1450. Российские газопроводы @ Timus Online Judge

THE_SCORPION TLE 17 [4] // Задача 1450. Российские газопроводы 30 сен 2006 19:13

My program works very quickly, but I have time limit.
I tested my programm many times. In all test time working is not more than 0,2 sec(even with 500 tops and 124750 edges).
Maybe somebody can tell me what is thе 17 test or what is the special trick in this test?

Kaliningrad SU -J_A_MES-HeadLiner Re: TLE 17 [3] // Задача 1450. Российские газопроводы 30 сен 2006 21:39

Use DP with presorting of course

Edited by author 30.09.2006 21:42

Eternal Re: TLE 17 [2] // Задача 1450. Российские газопроводы 25 сен 2008 20:25

It's another problem, where i can TLE troubles with Java. I implemented fastest and correct(!) solution :
topological sort + relaxes according to resulting order of vertexes. It works in o(m + n) time, and executing time is very small (0.16 - 0.2 sec) on my computer. I also tried many classes of input/output, but nothing helps. Pls tell me, how can i AC it using Java...

Eternal Re: TLE 17 // Задача 1450. Российские газопроводы 29 сен 2008 12:34

OMG, I just wrote this algo using C++, and AC in 0.125. Your java compiler is very bad...

Rustam Re: TLE 17 // Задача 1450. Российские газопроводы 22 июн 2009 02:27

maybe you have problems with processing input/output(in java it's too slow)
i've used ford-bellman algorithm (0.380 sec)

Обсуждение задачи 1450. Российские газопроводы