How Floyd Warshall algorithm works for N=500 within 1 second?

212 Views Asked by At

I am learning graph theory, and I found a problem Shortest Route II on CSES website. https://cses.fi/problemset/task/1672/ is the problem. I found the problem could be solved using Floyd Warshall Algorithm and the time complexity for the algorithm is O(n^3). I am confused because here the constraints are N<=500, Time limit: 1s, so when N=500 the computations should be 500^3 = 125,000,000 and keeping in mind that in 1 second, 10^8 computations are performed, therefore it should at least take 1.25 seconds causing TLE, but the solution gets accepted. I want to learn what I am doing wrong in my calculations or understanding.

0

There are 0 best solutions below