CSES 1672 Shortest Routes II - Why Floyd-Warshall Fits

Shortest Routes II gives you $q$ queries for shortest paths. If $q$ is large, running Dijkstra for each query is too slow.

Instead, run Floyd-Warshall once in $O(n^3)$ to precompute all distances. Then answer each query in $O(1)$ by indexing the $dist$ array. Total time: $O(n^3 + q)$. This beats $O(q \cdot n \log n)$ when $q$ is large. The pattern is: expensive preprocessing, cheap queries. Recognize this pattern and you will know when to use Floyd-Warshall.

Space complexity is $O(n^2)$ for the data structures used.