CSES 1672 Shortest Routes II - Lessons

This problem teaches you that precomputation wins when you have many queries.

Instead of running Dijkstra $q$ times, run Floyd-Warshall once and answer queries in $O(1)$. This pattern applies to many problems: if you can afford $O(n^3)$ preprocessing, you can answer all-pairs queries immediately. The core insight is recognizing when the query count justifies expensive preprocessing. If $q > n$, Floyd-Warshall is usually the right choice.