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?

Use DP with presorting of course

Edited by author 30.09.2006 21:42

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...

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

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