CSES 1672 Shortest Routes II - Problem Statement

The problem asks: given a weighted graph with $n$ cities, $m$ roads, and $q$ queries, answer each query: what is the shortest distance from city $a$ to city $b$?

This is exactly the all-pairs shortest path problem. Run Floyd-Warshall once, then answer each query in $O(1)$. If no path exists, output $-1$. The constraints allow $n \leq 500$, which makes $O(n^3)$ feasible. This problem tests whether you recognize the all-pairs pattern.

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