Why? What is a key point of this task?

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.

Thx, I will try this way.