Discussion @ 1198. Jobbery @ Timus Online Judge

I'm using Warshall's algorithm, but TLE 21

Posted by Andrew Sboev 22 Jul 2012 19:18

Why? What is a key point of this task?

Re: I'm using Warshall's algorithm, but TLE 21

Posted by Artem Khyzha 23 Jul 2012 14:56

You can try to condense your graph first. It helped me to avoid TLE21 with my O(N^3) DFS and indeed would help your Floyd-Warshall.

However, I am not sure whether there is not a better solution — my time is 0.25s that is so far from the best 0.046s.

Re: I'm using Warshall's algorithm, but TLE 21

Posted by Andrew Sboev 25 Jul 2012 00:20

Thx, I will try this way.

Discussion of Problem 1198. Jobbery